¿Es computable cada problema NP-hard?

¿Se requiere que un problema NP-hard sea computable?

No lo creo, pero no estoy seguro.

No, un duro no necesita ser computable. La definición es bastante completa: un problema es -duro si ese problema que tiene una solución de poli-tiempo implica que cada problema en tiene una solución de poli-tiempo (es decir, existe una reducción a para cada problema en ).$NP$$L$$NP$$NP$$L$$NP$

Los problemas incontrolables son difíciles de resolver: supongamos que podríamos resolver uno en tiempo polinómico. Luego, usamos la prueba de que es incuestionable deducir que es computable y no computable, una contradicción. De esta falsedad, podemos derivar cualquier cosa, a saber, que existe un algoritmo de tiempo polinómico para cualquier problema de que estemos viendo.$NP$

Por ejemplo, consideremos el problema de la parada . Podemos reducir cualquier lenguaje a siguiente manera, suponiendo que tengamos un verificador de polytime que verifica si es un certificado para :$H$$NP$$A$$H$$f(s,c)$$c$$s\in A$

• Dadas de entrada$s$
• Constructo (pero no de ejecución) de la máquina de Turing , que toma la entrada intenta todos los certificados y se detiene si es un certificado que verifica que .$M$$x$$c$$c$$s\in A$
• Devuelve (es decir, devuelve verdadero si detiene en la entrada )$H(M,x)$$M$$x$

Por lo tanto, con una sola llamada a un algoritmo de poli-tiempo que resuelve el problema de detención, podemos resolver cualquier problema de en tiempo polinómico.$NP$

Tal reducción no es útil, porque todo lo que hace es decir si "si es falso, entonces algo". Ya sabemos que no existe un algoritmo de polytime para problemas inconfundibles.

Parece haber una considerable confusión en esta comunidad con respecto a esta pregunta. Daré una respuesta detallada con la esperanza de aclarar el agua e iluminar la relación entre la computabilidad y la dureza NP.

Primero, creo que ser claro y explícito sobre las diversas definiciones involucradas resolverá gran parte de la confusión.

Una cadena es una secuencia finita de caracteres de un alfabeto finito fijo.

Un problema de decisión es un conjunto de cadenas. (Este conjunto es típicamente infinito). Piense en el problema de decisión como pruebas de cadenas para alguna propiedad: las cadenas con la propiedad están en el conjunto y las cadenas sin la propiedad no lo están.

Supongamos que tenemos dos problemas de decisión, y . Digamos que es polinomial reducible en tiempo a si hay algún polinomio y algoritmo algún algoritmo tal que, para todas las cadenas ,$A$$B$$A$$B$$p(x)$$M$$s$

• Si proporciona con la entrada , detiene en menos de pasos (donde es la longitud de la cadena ) y genera una cadena .$M$$s$$M$$p(|s|)$$|s|$$s$$M(s)$
• $s$ está en si y sólo si M ( s ) es en B .$A$$M(s)$$B$

Un problema de decisión es NP-difícil si, para cada problema de decisión NP A , A es en tiempo polinomio irreducible a B .$B$$A$$A$$B$

Un problema de decisión es computable si hay un algoritmo , que, para todas las cadenas s ,$M$$s$

• Si proporciona con la entrada s , M se detiene y emite "sí" o "no".$M$$s$$M$
• La salida es "sí" si está en A y "no" de lo contrario.$s$$A$

Con las definiciones anteriores, podemos aclarar inmediatamente lo que creo que podría ser la raíz de la confusión en su pregunta: nada en las definiciones de problema de decisión, reducciones o dureza NP requiere que los problemas de decisión sean computables. Las definiciones tienen mucho sentido pensando en los problemas de decisión como conjuntos arbitrarios de cadenas, y estos conjuntos pueden ser muy desagradables.

Eso deja dos preguntas sobre la mesa:

1. Las definiciones dejan abierta la posibilidad de que las funciones no computables sean NP-hard. ¿Existen en realidad funciones NP-hard no computables?
2. Existe la intuición de que decir que un problema es NP-hard es decir que es difícil de resolver. Decir que no es computable es como decir que es "realmente difícil" de resolver. Entonces, ¿ todos los problemas no computables son NP-hard?

La pregunta 1 es más fácil de responder. Hay dos formas particularmente importantes de encontrar problemas de decisión no computables que son NP-hard. El primero es el problema de la parada: el problema de la parada, , tiene la propiedad de que cada computable problema de decisión es en tiempo polinomio irreducible a H . Dado que los problemas de NP son computables, cada problema de NP es reducible en tiempo polinomial a H , entonces H es NP-duro.$H$$H$$H$$H$

La otra forma importante de construir un problema NP-hard no computable es observar que podemos combinar cualquier problema NP-hard conocido con cualquier problema no computable conocido. Deje que sea ​​NP-hard y B sea ​​no computable. Forme el problema de decisión A ⊕ B de la siguiente manera: A ⊕ B contiene esas cadenas de la forma "0, seguidas de una cadena en A " y las de la forma "1, seguida de una cadena en B ". A ⊕ B es NP-duro porque podemos convertir cualquier reducción (de cualquier problema) a A en una reducción a A ⊕ $A$$B$$A \oplus B$$A \oplus B$$A$$B$$A \oplus B$$A$$A \oplus B$: simplemente modifique el algoritmo para generar un "0" adicional al frente de su cadena de salida. no es computable, ya que calcular A ⊕ B requiere decidir qué cadenas que comienzan con "1" están en el conjunto; Esto es imposible, ya que B no es computable.$A \oplus B$$A \oplus B$$B$

La pregunta 2 es considerablemente más complicada, pero de hecho hay problemas de decisión no computables que no son NP-hard (suponiendo P NP). La buena respuesta de Yuval construye tal problema de decisión explícitamente. (Para cualquier teórico de la computabilidad en la sala, cualquier "Cohen Π 0 1- genérico" también funcionará). Analizaré por qué la intuición de que "los problemas NP-difíciles son difíciles, los problemas no computables son más difíciles " Está Mal.$\neq$$\Pi^0_1$

La dureza NP y la no computabilidad dicen que un problema es "difícil" en un sentido muy general, pero son muy diferentes y no deberían agruparse como el mismo tipo de fenómeno. Específicamente, la dureza NP es una propiedad "positiva": un problema NP difícil es difícil en el sentido de que, dado el acceso a una hoja de trucos para A , puede resolver una clase difícil de problemas$A$$A$ . Por otro lado, la no computabilidad es una propiedad "negativa": un problema no computable difícil en el sentido de que no se puede resolver A con una clase dada de recursos$A$$A$ .

( "Forzar", por cierto, es la técnica utilizada para producir el "Cohen genérico" que he mencionado. Para ser muy muy vaga, forzando está de manera general para producir cosas que son "genérico" en que tienen sin propiedades positivas y todas las propiedades negativas, por eso forzar puede producir directamente un problema que no es computable ni NP-hard).$\Pi^0_1$

No NP-Hard significa que es tan difícil o más difícil que los problemas NP más difíciles. Intuitivamente, ser incuestionable hará que sea mucho más difícil que NP.

Wikipedia:

Hay problemas de decisión que son NP-hard pero no NP-complete, por ejemplo, el problema de detención.

Todos saben que no es computable

Para completar, demostremos el siguiente teorema:

$\neq$

$\emptyset,\{0,1\}^*$

$\neq$$T_i$$L$$\{0,1,?\}$$\{0,1\}^*$$L$$0$$L$$1$$L$$?$$?$

$2i$$T_i$$T_i$$T_i$$x$$L(x) = ?$$L(x) := 0$$T_i(x)$$L(x) := 1$$T_i(x)$

$2i+1$$T_i$$T_i$$T_i$$x$$L(T_i(x)) = ?$$x \in \mathrm{SAT}$$x$$L(x) := 0$$L(x) := 1$

$\{0,1,?\}$$\{0,1\}^*$

$L$$2i$$T_i$$T_i$$L$$T_i$$T_i$$L$$T_i$$\neq$$T_i$$2i+1$$L$

$L$$L' \in \mathrm{NP}$$L'$$L$

$L' \in \mathrm{NP}$$L'$$M'$$f$$L'$$A_{\mathsf{NTM}}$

Creo que lo que hace que las personas piensen que no hay un problema NP-hard incuestionable es que pierden el punto de que la dureza NP es un límite inferior de la dureza de un problema, no un límite superior de su dureza como P o NP.

Un lenguaje L siendo NP-hard significa que está por encima del lenguaje en NP y eso es. Ahora, si comprende esto, lo que necesita es demostrar que hay un problema arbitrario más difícil.

$A$$A$$\mathsf{C}^A$$\mathsf{C}^A$$Halt_{\mathsf{C}^A}$$\mathsf{C}^A$

$A$$A'$$A < A'$$A<A'<A''<A'''<...$