Sobre la demostrabilidad de P versus NP

En primer lugar, mi comprensión del teorema de incompletitud de Gödel (y la lógica formal en general) es muy ingenua, también es mi conocimiento en informática teórica (lo que significa que solo tomé un curso de posgrado mientras aún estoy en la universidad), por lo que esta pregunta puede ser Muy ingenuo.

Por lo que pude encontrar, la probabilidad de P frente a NP es un problema abierto.

Ahora:

El primer teorema de incompletitud de Gödel establece que puede haber afirmaciones que son verdaderas pero no demostrables ni refutables.
Si se encuentra una solución polinómica para un problema de NP completo, prueba que P = NP.

Entonces, suponga que P = NP no es demostrable:
esto significa que no se puede encontrar ningún ejemplo de una solución polinómica para un problema NP-completo (de lo contrario, esto sería una prueba).
Pero si no se puede encontrar un ejemplo de una solución polinómica para un problema NP-completo, esto significa que P = NP es falso (lo demuestra, lo que significa que la declaración es demostrable), lo que lleva a una contradicción, por lo tanto P = NP debería ser demostrable .

Esto suena como una prueba de la demostrabilidad de P = NP para mí, pero creo que es extremadamente probable que se deba a mi falta de comprensión de los temas lógicos involucrados. ¿Podría alguien ayudarme a entender qué hay de malo en esto?

np-hardness proofs p-vs-np Alvaro
fuente

Ver el artículo de Scott Aaronson "¿Es P versus NP formalmente independiente?"

Marzio De Biasi

Parece ser que tengo una confusión más básica sobre cómo algo puede ser cierto pero no demostrable. Consulte el recorrido y el centro de ayuda para conocer el alcance de este sitio. Creo que esto es más adecuado para la informática o las matemáticas .

Kaveh

este papel semifamous Las pruebas naturales de Razborov / Rudich son aplicables a esta pregunta

vzn

Usted también puede estar interesado en la monografía Hartmanis' 'Cálculos factible y demostrable Complejidad Propiedades' que trata esencialmente lo que ocurre si sólo tenemos en cuenta los problemas que son demostrablemente en P, demostrable en NP, etc.

Joshua Grochow

Respuestas:

Si P = NP, debe haber algoritmos de tiempo polinómico para problemas de NP completo. Sin embargo, puede que no haya ningún algoritmo que resuelva un problema NP-completo y que se ejecute en tiempo polinómico.

David Richerby
fuente

Entonces, lo que está diciendo es que la falla es que puede haber un ejemplo de una solución polinómica, pero es posible que no pueda probar que es polinomial. Porque entonces no se considera en la prueba con el ejemplo, por lo que todavía no veo la falla.

Alvaro

Suponga que P = NP pero esto no es demostrable. Esto significa que hay un algoritmo de tiempo polinomial A para 3-SAT. Si pudieras probar que A era un algoritmo de poli-tiempo para 3-SAT, eso contradiría la falta de demostrabilidad de P = NP. Por lo tanto, aunque es cierto que A se ejecuta en tiempo polinómico y es cierto que A resuelve 3-SAT, al menos uno de estos hechos no se puede probar. Para expresarlo en los términos de la pregunta, el hecho de que un algoritmo de poli-tiempo para 3-SAT existe no implica que se pueda "encontrar".

David Richerby

Entonces, el "Pero si no se puede encontrar un ejemplo de una solución polinómica para un problema NP-completo, esto significa que P = NP es falso", ¿está mal, porque puede haber una solución aunque no se pueda encontrar?

Alvaro

Eso es correcto.

David Richerby

M

$M$

c

$c$

N

$N$

n \geq N

$n \geq N$

n

$n$

M

$M$

n^{c}

$n^c$

$\neq$

Tpecatte
fuente