¿Es posible que no se pueda demostrar que P != NP?

Question

Probablemente estoy haciendo una pregunta estúpida, pero lo que deduzco de una explicación no especializada del teorema de incompletitud de Godel es que es completamente posible que un enunciado verdadero no pueda derivarse del teorema y los axiomas.

Mientras que todas las pruebas apuntan a que P != NP. ¿No es posible que no se pueda demostrar después de todo porque el propio sistema es incompleto?

P.D.: Todo lo que he entendido proviene de los cuatro primeros capítulos del GEB de Douglas Hofstadter.

Answer 1

Sí, en nuestro estado actual de conocimientos es ciertamente concebible que P=NP sea independiente de cualquier fundamento axiomático dado para las matemáticas (como la Aritmética de Peano o ZFC). Incluso podría ser "independiente de los axiomas, pero no demostrable".

A diferencia de otras sentencias enigmáticas, saber que P=NP es independiente de los axiomas no nos ayudaría en sí mismo a averiguar si es en realidad verdadero o falso. Esto podría contrastarse, por ejemplo, con la conjetura de Goldbach: la única forma de que sea independiente es que sea realmente cierta.

El estudio de Araronson que @fgp encontró parece excelente.