Los ejemplos comunes de problemas NP-difíciles (camarilla, 3-SAT, cubierta de vértice, etc.) son del tipo en el que no sabemos si la respuesta es "sí" o "no" de antemano.
Supongamos que tenemos un problema en el que sabemos que la respuesta es sí, además, podemos verificar un testigo en tiempo polinómico.
¿Podemos siempre encontrar un testigo en tiempo polinómico? ¿O puede este "problema de búsqueda" ser NP-hard?
Respuestas:
TFNP es la clase de funciones de valores múltiples con valores que se verifican polinómicamente y se garantiza que existan.
Existe un problema en TFNP que es FNP completo si y solo si NP = co-NP, consulte el Teorema 2.1 en:
Nimrod Megiddo y Christos H. Papadimitriou. 1991. Sobre funciones totales, teoremas de existencia y complejidad computacional. Theor Comput Sci. 81, 2 (abril de 1991), 317-324. DOI: 10.1016 / 0304-3975 (91) 90200-L
y las referencias [6] y [11] dentro. PDF disponible aquí .
fuente
No, no siempre puede encontrar una solución en tiempo polinómico, incluso si sabe que hay una solución.
Según Khanna, Linial y Safra [1] (ver el 3er párrafo), del trabajo clásico de 1972 de Karp se deduce que colorear un gráfico de 3 colores con 3 colores es NP-duro. (Su trabajo extiende esto para mostrar que los gráficos de 4 colores y 3 colores aún son NP-hard).
Tenga en cuenta que esto no contradice la respuesta de Rahul Savani . Esto se debe a que para todas las relaciones binarias en FNP, debemos poder verificar en tiempo polinómico si está en la relación. Dado que decidir si un gráfico de 3 colores con 3 colores es NP completo, es poco probable que el problema de encontrar un color de 4 en un gráfico de 3 colores esté en FNP ya que no podemos verificar la validez de la entrada en tiempo polinómico . Por lo tanto, no hay contradicción con el resultado Megiddo-Papadimitriou.P ( x , y ) xPAGS PAGS( x , y) X
[1] Khanna, Sanjeev, Nathan Linial y Shmuel Safra. "Sobre la dureza de aproximar el número cromático". Teoría y Sistemas de Computación, 1993., Actas del 2º Simposio de Israel sobre el. IEEE, 1993.
fuente
Si una relación NP es NP-dura con respecto anortePAGS= c o NPAGS .
las reducciones de Turing de tiempo polinomial co-no determinista de solo respuesta sí , entonces
Prueba:
si una relación NP es NP-dura con respecto a
las reducciones de Turing de tiempo polinomial co-no determinista de solo respuesta sí , entonces:
Así
Por simetría,
Por lo tanto, si una relación NP es NP-dura con respecto a
las reducciones de Turing de tiempo polinomial co-no determinista de solo respuesta sí , entonces
fuente
fuente