El problema P vs NP es uno de los problemas más difíciles en informática teórica.
P contra NP
Por lo general, puede consultar una solución a un problema. Ya sea usando la multiplicación para la división o conectando la respuesta de una variable, los profesores de matemáticas te dicen que verifiques tu trabajo usando tu respuesta en cada clase de matemáticas en la escuela.
Pero digamos que puede verificar fácilmente una solución, ¿es igual de fácil resolver esta solución?
Este es el problema de P contra NP, un problema de premio del milenio donde el solucionador recibirá un millón de dólares si se proporciona una prueba válida.
¿Qué es P versus NP?
En informática, la eficiencia de los algoritmos es muy importante. La mayoría de los algoritmos se consideran “rápidos” si pueden resolverse dentro de un estándar llamado tiempo polinomial. El tiempo polinomial ocurre cuando un problema se puede resolver en pasos escalados por un factor de un polinomio dada la complejidad de la entrada. Entonces, digamos que la complejidad de la entrada es un número n, un algoritmo de tiempo polinomial podrá resolver un problema en nk no.
Esencialmente, P vs NP hace la pregunta: ¿Los problemas cuyas soluciones se pueden verificar en tiempo polinomial también tienen sus respuestas resueltas en tiempo polinomial?
NP-Completitud
Un diagrama de Euler que muestra los casos de NP-Completitud para P ≠ NP y P = NP. Crédito: Behnam Esfahbod, Wikimedia Commons (CC-BY 3.0)
Uno de los subproblemas más importantes es el de los problemas NP-completos. Los problemas NP-completos son aquellos que se pueden verificar rápidamente y se pueden usar para simular todos los demás problemas NP-completos. Por lo tanto, resolver cualquiera de estos problemas en tiempo polinomial es un gran impulso para resolver P vs NP. Algunos de estos problemas incluyen juegos como Battleship y la solución óptima a un Cubo de Rubik NxNxN, pero también incluyen preguntas teóricas famosas como el problema del viajante de comercio. Si se encuentra una solución para uno de ellos, también se puede encontrar una solución general para problemas NP-completos.
Impacto
Si se demuestra que P es igual a NP, podría haber graves consecuencias y beneficios. La ciberseguridad sería un gran problema, ya que se interrumpiría la criptografía de clave pública y se podrían piratear muchos cifrados. Sin embargo, también habría mejoras en la investigación de la predicción de la estructura de proteínas y la computación global a través de una mejor programación de enteros y la resolución del problema del viajante de comercio.
Si se demuestra que P no es igual a NP, casi no habría desventajas ni ventajas. Entonces, los investigadores se centrarían menos en una solución general para todos los problemas NP-completos, lo que no cambiaría mucho.
Clausura
P vs NP es un problema crítico sin resolver en informática que podría tener efectos drásticos. Aunque el mayor consenso es que P no es igual a NP, cualquier prueba ampliamente aceptada sacudiría al mundo científico.
Referencias:
- “El problema P vs NP” por Stephen Cook, 2001, claymath.org
- “Computadoras e intratabilidad: una guía para la teoría de la integridad de NP” por Michael Garey, David S Johnson, 1979, ISBN 0-7167-1045-5
