¿Hay algún obstáculo conocido para algún enfoque para resolver P vs. NP?

Question

¿Existe algún obstáculo conocido para demostrar el siguiente invariante (quizás por algún tipo de inducción)?

Dejemos que $\Sigma$ sea algún alfabeto finito con $|\Sigma| \geq 2$ , dejemos que $M$ sea una máquina de Turing determinista (decidora) con un alfabeto de entrada $\Sigma$ y que $L_0 \subseteq \Sigma^{\star}$ sea algo no disperso, $\mbox{NP}$ -lengua completa.
Entonces se cumple al menos una de las siguientes propiedades:

1. $M$ no termina siempre.
2. $M$ tiene una complejidad de tiempo superpolinomial.
3. $L(M) \triangle L_0$ no es escaso.

Descripción concisa del problema: $\mbox{NP} \not\subseteq \mbox{P-close}$ (según Tsuyoshi Ito, véase su respuesta).

Precaución: Este problema es equivalente a $\mbox{P} \neq \mbox{NP}$ .

Answer 1

Esta es una versión algo más detallada de algunos de mis comentarios sobre su publicación cruzada en cstheory.stackexchange.com .

El enunciado que has descrito se puede escribir de forma concisa como NP ⊈ P-cerrado. Aquí P-close es la clase de problemas de decisión para los que existe un algoritmo A de tiempo polinómico tal que el conjunto de instancias en las que A no responde correctamente es escaso.

Es fácil ver que P ⊆ P-close ⊆ P/poly, de lo cual es fácil ver que las implicaciones sostienen que NP ⊈ P/poly ⇒ NP ⊈ P-close ⇒ P≠NP. Como NP ⊈ P-cerrar implica P≠NP, cualquier prueba de NP ⊈ P-cerrar debe superar también la barrera de relativización y la barrera de algebrización. No sé si la barrera de la prueba natural (que toda prueba de NP ⊈ P/poly debe superar) se aplica necesariamente a NP ⊈ P-close.

No creo que se sepa que NP ⊈ P-cerrado sea equivalente a P≠NP como afirmas.

---

Editar : Al contrario de lo que escribí en una revisión anterior, me enteré de que NP ⊈ P-close es efectivamente equivalente a P≠NP. Aunque ya respondí a tu pregunta sobre las barreras más arriba, supongo que escribir la prueba de esta equivalencia puede ser útil. La prueba se basa en lo que has descrito en cstheory.stackexchage.com con una modificación (concretamente, utilizo el resultado de Ogihara y Watanabe en lugar del teorema de Mahaney).

Como se ha dicho anteriormente, tenemos la implicación NP ⊈ P-cerrado ⇒ P≠NP. Demostraremos la inversa: NP ⊆ P-cerrar ⇒ P=NP.

A _tiempo polinómico k -reducción de la tabla de la verdad_ de una lengua L ₁ a una lengua L ₂ es una reducción de Turing a partir de L ₁ a L ₂ que invoca el oráculo como máximo k veces de forma no adaptativa. Nótese que una reducción de muchas veces es un caso especial de una reducción de 1 tabla de verdad. Ogihara y Watanabe [OW91] demostraron el siguiente resultado:

Teorema [OW91]. Si algún lenguaje disperso es NP-completo bajo tiempo polinomial k -reducibilidad de la tabla de la verdad para alguna constante k , entonces P=NP.

Nótese que este teorema generaliza Teorema de Mahaney , que es el caso especial del teorema en el que la reducción se restringe a una reducción polinómica de muchos elementos.

Supongamos que NP ⊆ P-close. Entonces SAT ∈ P-close. Equivalentemente, existe un lenguaje L ∈P tal que la diferencia simétrica S \=SAT△ L es escaso. Entonces, la siguiente es una reducción en tiempo polinómico de 1 tabla de verdad de SAT a S : dada una entrada x , decidir (en tiempo polinómico) si x ∈ L y decidir (invocando el oráculo para S ) si x ∈ S y devuelve el XOR de los dos resultados. Por lo tanto, el conjunto disperso S es NP-completo bajo la reducibilidad de la tabla de 1 verdad en tiempo polinomial. Esto implica que P=NP por el mencionado teorema de Ogihara y Watanabe.

[OW91] Mitsunori Ogihara y Osamu Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing , 20(3):471-483, junio de 1991. http://dx.doi.org/10.1137/0220030