Historia, pregunta formulada por eviledesma16, hace 1 año

qué es el P . A . N?​

Respuestas a la pregunta

Contestado por ronaldoskrrr
0

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.

Explicación:

Otras preguntas