Respuestas
Respuesta: la clase P es una de las más importantes; la clase N P consiste de todos aquellos problemas de decisión cuyas soluciones positivas/afirmativas pueden ser verificadas en tiempo polinómico a partir de ser alimentadas con la información apropiada, o en forma equivalente, cuya ...
Explicación paso a paso:
En esencia, la pregunta ¿es P = NP completo ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO por ejemplo, el problema de la suma de subconjuntos, que es un ejemplo de un problema fácil de verificar, pero cuya respuesta se «cree» (pero no ha sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números enteros, ¿existe un subconjunto no vacío de ellos donde la suma de sus elementos es igual a 0? por ejemplo, ¿Existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SÍ, si bien puede llevar algún tiempo encontrar un subconjunto que satisface el requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10, 15} es igual a cero», entonces lo podemos comprobar en forma muy rápida y mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un proceso mucho más rápido que encontrar el subconjunto. La información necesaria para verificar un resultado positivo/afirmativo es llamada un «certificado». Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo polinomial) y es esta la razón por la que el problema se encuentra en N P. Una respuesta a la pregunta P = N P sería determinar si en problemas del tipo SUMA-SUBCONJUNTO es tan fácil hallar la solución como verificarla. Si se encuentra que P no es igual a N P, ello significa que algunos problemas N P serían significativamente más difíciles de hallar su solución que verificar la misma. La respuesta sería aplicable a todo este tipo de problemas, no solo al ejemplo específico de SUMA-SUBCONJUNTO.
La restricción a problemas de tipo SÍ/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FNP = FP).