P vs NP y Gödel

Question

Me disculpo por el, tal vez, la pregunta tonta. Mi impresión, como laico, es que Gödel Teorema de la Incompletitud debe descartar la posibilidad de que P=NP. Es que la verdad o existen profundas implicaciones técnicas?

Answer 1

Voy a repetir lo que escribí más de MO:

Es cierto que no existe ningún algoritmo para determinar si es o no $T$ es demostrado por el PA, y que la prueba de esto es muy cercano a la prueba de que el teorema de Gödel. Si hubo un polinomio $p$ de manera tal que cada teorema de longitud $K$ tenía una prueba de la longitud de la $p(K)$, esto estaría en contradicción con el anterior hecho. (Tratando de cada prueba de la longitud de la $p(K)$ sería un algoritmo.)

También es cierto que, si P=NP, no es un polinomio de tiempo del algoritmo de tal manera que, si $T$ tiene una prueba de la longitud de la $N$, entonces este algoritmo encuentra una prueba de la longitud de la $q(N)$, para algún polinomio $q$.

Estos dos hechos no están en contradicción, porque el primero es acerca de las pruebas de longitud polinomial en el tamaño del teorema, y la segunda es sobre las pruebas polinomial en el tamaño de alguna otra prueba.

Answer 2

No hay ninguna razón para pensar que los teoremas de la incompletitud tienen ninguna influencia en la cuestión de si $P=NP$, y no el trabajo actual ha establecido ninguna relación entre ellos.

Answer 3

Diagonalización funcionado bien para el teorema de Gödel, pero la búsqueda a utilizar para resolver el P versus NP pregunta ha sido descartado por la Baker-Gill-Solovay teorema.