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
- ¿Qué es O (nlog (n)) de notación big-O? ¿Cuáles son algunos ejemplos de sus algoritmos?
- Ciencias de la computación teóricas: ¿Hay una prueba para: "La mejora personal recursiva es posible"?
- ¿Debo especializarme en informática teórica o aprendizaje automático?
- Cómo diseñar una máquina de Turing con este RE a ^ (2n + 1) b ^ (2n-1)
- ¿La comunidad académica evita los intentos de resolver un problema NP-difícil en tiempo polinómico?
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)