¿Es posible que alguien demuestre que P = NP es imposible de probar o refutar?

Answer 1

Sí, es posible, y varias personas piensan que es el resultado más probable. Sin embargo, hay una advertencia importante.

Hay ejemplos de problemas matemáticos famosos que han demostrado ser indecidibles (lo que significa que no se pueden probar ni refutar con las matemáticas convencionales). Probablemente el ejemplo más famoso sea la hipótesis del continuo. Por lo tanto, no es en absoluto improbable que P contra NP sea el próximo gran problema que se convierta en indecidible.

La advertencia es que cada prueba de decidibilidad debe comenzar por corregir lo que se entiende por “matemáticas convencionales”, es decir, qué axiomas y resultados de inferencia se permiten para que un argumento cuente como una prueba. Existe una opción estándar, llamada teoría de conjuntos de Zermelo-Fraenkel (ZFC), y la prueba de que la Hipótesis del Continuo es indecidible equivale a demostrar que no se puede probar ni probar con el uso de ZFC.

Sin embargo, otros sistemas de axiomas son posibles. De hecho, muchos lógicos no consideran que la hipótesis del continuo esté resuelta, y en su lugar creen que nuestra tarea consiste ahora en encontrar la alternativa correcta a la ZFC, en la cual la hipótesis del continuo se puede probar o refutar.

Sin embargo, hay una diferencia interesante entre una pregunta como la hipótesis del continuo y P versus NP: la mayoría de las personas estarían de acuerdo en que definitivamente existe un hecho importante acerca de P versus NP, independientemente de los axiomas que nos gusta usar para hacer matemáticas. El estado de la hipótesis del continuo depende de lo que entendemos por la palabra “conjunto” (sorprendentemente vaga), pero o bien hay una máquina de Turing que resuelve 3-SAT en el tiempo polinomial o no existe. No hay espacio para afirmar que “depende de los axiomas que use”.

Entonces, una prueba de que P versus NP es indecidible es una posibilidad muy real, pero no sería el final de la historia. Siempre habría la posibilidad de que luego se introdujera un nuevo sistema de axiomas, más fuerte que ZFC, que podría resolver P versus NP.

Answer 2

No puede probar ni refutar P = NP sin conocer el valor de N y P. Sin embargo, no importa qué P es si N = 1. Dejame explicar.

Si N = 1, entonces P = NP es correcto, sin importar el valor de P. Algunos pueden argumentar que si P = 0 y N = 1, entonces la ecuación es falsa. Esto está mal. 0 = 1 * 0. Simplemente no dividas por 0 y estás bien. Pero debería ser obvio que hacer algo matemáticamente ilegal a una ecuación no lo refuta.

Si N no es igual a 1, entonces la ecuación anterior es incorrecta, excepto si P = 0. Si P = 0 entonces no puedes resolver N.

La ecuación en sí no tiene sentido realmente. Porque si N = 1, entonces N = 1 es la expresión simplificada de P = NP (excepto si P = 0). Y si N no es igual a 1, entonces la ecuación es incorrecta y, por lo tanto, sin sentido (excepto si P = 0). Y si P = 0, entonces no nos importa lo que N es igual, porque todos podemos estar de acuerdo en que 0 = 0 no importa por lo que multipliques cero.

Answer 3

Sí, eso ciertamente parece posible.