Clases de problemas P y NP

Qué se debe demostrar para establecer la validez de una reducción polinómial?

• Que la reducción se puede realizar en tiempo polinómial.

• Que el problema es NP-completo.

• Que la reducción mapea instancias correctamente.

• Que la reducción reduce la complejidad del problema.

Cuáles son las clases de complejidad a la que pertenece un problema que se puede verificar en tiempo polinomial?

• P

• NP

• NP-Completo

• NP-Dificil

Cuál es el rol de un certificado en la demostración de que un problema pertenece a NP?

• Probar que un problema es polinomial

• Probar que un problema es decidible.

• Probar que una solución propuesta es correcta.

• Probar que un problema es soluble.

Qué se debe demostrar para mostrar que un problema pertenece a la clase NP?

• Que todas las instancias del problema tienen solución.

• Que una solución para el problema se puede verificar en tiempo polinomial

• Que todas las soluciones del problema son óptimas.

• Que el problema no se resuelve en tiempo polinomial.

Cuál es la relación entre un problema candidato a ser NP-completo y un problema NP-completo conocido en una reducción polinómica?

• El problema candidato se reduce al problema conocido.

• El problema conocido se reduce al problema candidato.

• Ambos problemas se resuelven en tiempo polinomial.

• Ambos problemas pertenecen a la clase P.

Qué significa NP en teoría de la computación?

• No Poliniomial

• No Practicable

• No Problema

• Nondeterministic Polynomial

Qué significa que un problema sea NP-completo?

• Que es un problema muy difícil de resolver.

• Que es un problema que solo puede ser verificado en tiempo exponencial.

• Que es un problema que puede ser reducido a cualquier otro problema en NP.

• Que es un problema que puede ser reducido desde cualquier otro problema en NP.

Cuál de las siguientes afirmaciones sobre la clase P es verdadera?

• NP es un subconjunto de P.

• P es un subconjunto de NP.

• P y NP son conjuntos disjuntos.

• NP y P son lo mismo.

Qué es una instancia de un problema?

• Una solución propuesta para el problema.

• Un caso particular o ejemplo del problema

• Una medida de la complejidad del problema.

• Una forma de reducir la complejidad del problema.

Cuál es el objetivo principal de la teoría de la NP-completitud?

• Encontrar algoritmos eficientes para problemas en la clase NP.

• Clasificar problemas en términos de su dificultad computacional.

• Demostrar que todos los problemas son NP-completos.

• Probar que la clase P es igual a la clase NP.