Informática, pregunta formulada por joanbles, hace 1 año

Determina si todo problema NP también es un problema P, es decir si P=NP

Respuestas a la pregunta

Contestado por marbellasaenzsanchez
6

La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta ¿es P = NP completo ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?

Los recursos comúnmente estudiados en complejidad computacional son:

– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.

– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...). Este artículo se centrará en las clases P y NP.

Se considera el problema más importante en este campo, el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quien desarrolle la primera demostración correcta.

Contestado por elsabelotodo1233
2

Respuesta:

ese no es de la pagina de los problemas que no tienen respuesta?

Explicación:

Otras preguntas