Clases de problemas P y NP
Authored by Brian Curcio
Mathematics
University
Used 2+ times
AI Actions
Add similar questions
Adjust reading levels
Convert to real-world scenario
Translate activity
More...
Content View
Student View
12 questions
Show all answers
1.
MULTIPLE SELECT QUESTION
45 sec • 1 pt
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.
2.
MULTIPLE SELECT QUESTION
45 sec • 1 pt
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
3.
MULTIPLE SELECT QUESTION
45 sec • 1 pt
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.
4.
MULTIPLE SELECT QUESTION
45 sec • 1 pt
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.
5.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
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.
6.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Qué significa NP en teoría de la computación?
No Poliniomial
No Practicable
No Problema
Nondeterministic Polynomial
7.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
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.
Access all questions and much more by creating a free account
Create resources
Host any resource
Get auto-graded reports
Continue with Google
Continue with Email
Continue with Classlink
Continue with Clever
or continue with
Microsoft
%20(1).png)
Apple
Others
Already have an account?
