¿Por qué P no es igual a NP es tan difícil de probar?

Vea la entrada de wikipedia sobre P versus NP (sección sobre complejidad de la prueba)

¿La versión corta es que P (no) igual a NP? Es una de las preguntas más importantes en la informática teórica. Muchas personas brillantes han trabajado en ello y todavía no tienen pruebas claras. El consenso parece ser que tal prueba no se puede escribir utilizando los sistemas de axiomas existentes.

Por ejemplo, un artículo brillante de Razborov y Rudich utiliza una noción de ‘prueba natural’ para mostrar que si hay una prueba natural de que P no es igual a NP, entonces el problema del logaritmo discreto se puede resolver en un tiempo relativamente corto de computadora ( lo que implica, entre otras cosas, que no es demasiado difícil factorizar enteros grandes). Como se cree ampliamente que no existe un algoritmo rápido para el problema del logaritmo discreto, parece muy poco probable que exista una prueba natural de que P no sea igual a NP

Entonces, para probar que P (no) es igual a NP, uno tendría que inventar un nuevo sistema de axiomas lo suficientemente expresivo como para capturar la complejidad computacional y luego escribir la prueba (si existe)

Porque en la lógica tradicional, ‘no no P’ no era igual a P.

Puede probar que P es probable, pero no prueba que el caso sea exactamente como P.

Dice que P no existe, pero no dice que existe. Algunos dicen que la única forma de ‘probar’ P es afirmar que P.

En mi lógica, la respuesta es evitar la lógica de premisas, ya que de todos modos se puede contradecir, y centrarse en la exclusión y la asociación inherente a través de coordenadas cartesianas limitadas y opuestos opuestos en la diagonal. Ver deducción categórica. ¿Qué es la deducción categórica?

Es difícil probar P! = NP porque solo necesitamos un contraejemplo para refutar esto.

Se puede demostrar que todos los problemas con NP completo se pueden completar dentro de un límite polinómico de otros problemas con NP completo. Como resultado, un único problema en NP-complete tiene una solución de tiempo polinomial que probaría que todos los problemas de NP se pueden resolver en tiempo polinómico ya que los problemas de NP-complete son los más difíciles en NP.

Como resultado, probar que P! = NP significaría que se debe demostrar que todos los posibles problemas de NP completo no tienen una solución de P. Algunos creen que P! = NP es indecidible y solo P = NP es un problema decidible.

Porque nadie ha transformado un problema NP-difícil en un problema P en tiempo polinómico