¿Por qué el segundo teorema de incompletitud de Godel no descarta una prueba formalizable de P! = NP?

Estoy seguro de que debe haber algo incorrecto con el siguiente razonamiento porque, de lo contrario, se reduciría mucha investigación de P vs. NP, pero no puedo determinar mi error:

Para cualquier entero fijo defina $k>0$

{si}_{k} : = {⟨ φ ⟩ El | φ es un wff de ZF y tiene una prueba de longitud \leq k {El | φ El |}^{k}}

$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$

Ahora para todos los , el lenguaje está en NP ya que una prueba válida para de longitud puede ser un testigo NP verificado por un verificador de pruebas automatizado en tiempo polinómico. Además, para suficientemente grande , es NP-completo ya que SAT se reduce a eso: es decir, para una instancia de SAT, haga un wff correspondiente de ZF usando cuantificadores existenciales. Entonces, una asignación de verdad satisfactoria de puede convertirse en una prueba formal de de polinomio de longitud endesde una asignación de verdad de $k$ $B_k$ $\varphi$ $\leq k{|\varphi|}^k$ $k$ $B_k$ $\phi$ $\varphi$ $\phi$ $\varphi$ $|\varphi|$ $\phi$ es lineal en. $|\phi|$

Ahora, si ZF es inconsistente, esto significa que hay una declaración formal tal que tanto como tienen pruebas en ZF. Como es bien sabido, cualquier otra declaración puede derivarse de la conjunción contradictoria (es decir, siguiendo la ruta: $\sigma$ $\sigma$ $\neg \sigma$ $\tau$ $\langle \sigma \wedge \neg \sigma \rangle$

⟨ σ \land \neg σ ⟩ ⟹ ambos σ y \neg σ son verdaderas ⟹ ⟨ \neg τ \to σ ⟩ es cierto (ya que independientemente de τ la implicación es válida desde σ es verdad) ⟹ ⟨ \neg σ \to τ ⟩ (por contraposición y doble negación) ⟹ τ es cierto (por modus ponens con \neg σ)

$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau \; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$

) Por lo tanto, si ZF es inconsistente, entonces cada instrucción tiene un polinomio de prueba (me parece incluso lineal) en. $\varphi$ $|\varphi|$

Sea para un suficientemente grande como se mencionó anteriormente para permitir que sea NP-completo. Entonces, si ZF es inconsistente, solo hay finitamente muchos tales que porque la tolerancia de longitud de prueba polinómica de alto grado de es suficiente para cubrir las pruebas cortas garantizadas de wffs de longitud suficiente. Esto implica que es decidible en tiempo polinómico, lo que por su integridad NP implica que P = NP. Si reformulamos esta cadena de razonamiento en términos de contrapositivos, si P! = NP, entonces ZF no es inconsistente (es decir, es consistente). $B:=B_k$ $k$ $B$ $\varphi$ $\langle \varphi \rangle \notin B$ $B$ $B$

Por lo tanto, si tenemos una prueba formal de P! = NP, entonces tenemos una prueba formal de la consistencia de ZF. Pero según el segundo teorema de incompletitud de Godel, esto implica que ZF es inconsistente, lo que a su vez obtiene P = NP como se describe anteriormente (así como la teorema de cualquier teorema negado).

Esto no es exactamente una prueba de que P vs. NP es independiente de ZF. Podría ser que ZF sea consistente y que P = NP o que P! = NP se pueda probar mediante técnicas no formalizables dentro de ZF. Sin embargo, presenta otra barrera formidable para resolver P vs. NP.

complexity-theory np-complete logic p-vs-np Ari
fuente

Respuestas:

Parece que hay un defecto aludido por Arno en su respuesta. Si bien la reducción parece lo suficientemente inocuo (y de hecho es un ejercicio de libro de texto como lo señala Ariel en su comentario), asume implícitamente la consistencia de ZF. De lo contrario, si ZF es inconsistente, ya que cada declaración de ZF tendría una prueba, las instancias SAT insatisfactorias no se asignarían necesariamente a wffs que no tienen una prueba relativamente corta. $SAT \leq B$ $\varphi$

Por lo tanto, si suponemos que ZF es consistente y entonces, aunque podemos concluir metamatemáticamente que (porque siendo NP completo, no podría estar en ya que estamos asumiendo ) no tendríamos una deducción formal de (ya que esto depende de que sea un conjunto NP-completo establecido, por lo que si queremos usar la reducción anterior, debemos suponer que ZF es consistente, lo que no puede ser afirmado formalmente por el segundo teorema de incompletitud de Godel). Por lo tanto, este argumento no puede sugerir ninguna implicación necesaria de . $ZF \vdash P \neq NP$ $B \notin P$ $B$ $P$ $P \neq NP$ $ZF \vdash B \notin P$ $B$ $ZF \vdash P \neq NP$

Ari
fuente

¡Buen trabajo! Este parece ser el problema.

Ariel

El problema está en su afirmación de que para suficientemente grande , el lenguaje es NP-completo. En su reducción propuesta, solo argumenta que cualquier instancia SAT satisfactoria es una fórmula ZF con prueba "corta". Sin embargo, también debe argumentar que siempre que la fórmula ZF resultante tenga una prueba corta, entonces la instancia SAT original es satisfactoria. Por supuesto, esto se reduce a decir que si ZF demuestra que la instancia SAT es satisfactoria, entonces realmente lo es, pero aquí estamos usando la solidez de ZF. $k$ $B_k$

Arno
fuente

Tienes razón en que supongo implícitamente la solidez de ZF y la corrección de un comprobador de pruebas, pero ¿cómo afecta esto a la prueba de que es NP-completo? Estos son solo supuestos necesarios para que el lenguaje sea de interés. Bajo mi reducción, solo una instancia SAT satisfactoria tendrá una prueba de cualquier longitud porque una insatisfactoria corresponde a una declaración ZF que es falsa.

B_{k}

$B_k$

B_{k}

$B_k$

Ari

@Ari Las instancias SAT insatisfactorias corresponden a declaraciones ZF que son falsas en su metateoría. Entonces, para que la reducción funcione, necesita que las declaraciones falsas de ZF no tengan una prueba de ZF.

Arno

La equivalencia es clara, si la fórmula tiene una prueba, entonces la instancia SAT es satisfactoria (ZF es sólido, no veo por qué esto debería ser un obstáculo aquí). Vea esta pregunta para una prueba de su integridad NP.

Ariel

@Ariel La respuesta en esa pregunta es imprecisa sobre cuáles son los supuestos. Necesariamente debe suponer que ZF es sólido. Solo el recordatorio: "Sonido" significa que si una declaración tiene una prueba, entonces es realmente cierto. Si ZF es inconsistente, entonces lo prueba todo y, por lo tanto, no puede ser sólido. En particular, vemos que "ZF es sonido" no es un teorema de ZF. Si nuestra meta-teoría demuestra que "ZF es sólido", entonces también demuestra que "ZF es consistente", y no hay problema. Si no lo prueba, entonces no tenemos la prueba de integridad de NP, y tampoco hay problema.

Arno

La corrección de la reducción se basa en la consistencia de ZF, sin embargo, no tiene nada que ver con la solidez. Recuerde que la solidez se define en relación con algunas semánticas, y ZF es sólido en el sentido de que las declaraciones demostrables son verdaderas en todos los modelos, si ZF es inconsistente de que es un sonido vacío ya que no tiene modelos.

Ariel