El problema P versus NP

El problema P versus NP pregunta si todo problema cuyas soluciones pueden verificarse rápidamente también puede resolverse rápidamente, la cuestión abierta central de la informática teórica y uno de los problemas del milenio de Clay.

Definition

P es la clase de problemas resolubles en tiempo polinómico, y NP la clase de problemas cuyas soluciones propuestas son verificables en tiempo polinómico; el problema P versus NP pregunta si estas dos clases son iguales, lo que se cumple si y solo si algún problema NP-completo es resoluble en tiempo polinómico.

Scope

Este tema cubre la declaración formal de P versus NP, su equivalencia a si cualquier problema NP-completo tiene un algoritmo de tiempo polinómico, las consecuencias de cualquiera de las respuestas, las barreras como la relativización, las pruebas naturales y la algebrización que han bloqueado el progreso, y la conjetura generalizada de que las clases difieren.

Core questions

• ¿Es encontrar una solución fundamentalmente más difícil que verificar una?
• ¿Por qué la respuesta depende de si algún problema NP-completo está en P?
• ¿Cómo sería el mundo si P fuera igual a NP, y si no lo fuera?
• ¿Por qué décadas de esfuerzo no han logrado resolver la cuestión?

Key theories

Equivalencia con la NP-completitud

P es igual a NP si y solo si cualquier problema NP-completo tiene un algoritmo de tiempo polinómico, por lo que la pregunta general se reduce a la tratabilidad de un único problema concreto como la satisfacibilidad.

Barreras de prueba

Los resultados de relativización, pruebas naturales y algebrización muestran que las principales técnicas de prueba conocidas no pueden resolver P versus NP, lo que explica la dificultad y guía la búsqueda de métodos fundamentalmente nuevos.

Clinical relevance

La presunta desigualdad de P y NP es la suposición de trabajo detrás de tratar los problemas NP-difíciles como intratables y detrás de la seguridad de la criptografía, ya que la resolución eficiente de problemas NP rompería la encriptación ampliamente utilizada; una prueba constructiva de que P es igual a NP transformaría la optimización, la logística y la ciencia.

History

Cook formuló la pregunta en 1971 junto con la NP-completitud, y rápidamente se reconoció como fundamental. Los intentos a través de límites inferiores de circuitos en la década de 1980 encontraron la barrera de las pruebas naturales identificada por Razborov y Rudich, y en 2000 el Clay Mathematics Institute lo nombró un problema del Milenio con un premio de un millón de dólares.

Debates

¿Se resolverá alguna vez P versus NP, y cuál es la respuesta?

La mayoría de los investigadores conjeturan que P no es igual a NP, pero no existe una prueba y las técnicas conocidas son demostrablemente insuficientes. Las opiniones difieren sobre si la resolución está cerca, requiere matemáticas radicalmente nuevas, o si la pregunta podría incluso ser independiente de los axiomas estándar.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

¿Qué pasaría si P fuera igual a NP?

Muchos problemas que ahora se consideran intratables, desde la programación óptima hasta la ruptura de códigos criptográficos, tendrían algoritmos eficientes, y el acto de encontrar soluciones no sería más difícil que verificarlas. Los efectos en el comercio, la seguridad y la ciencia serían profundos, lo cual es parte de la razón por la que la mayoría de los expertos esperan que P no sea igual a NP.

¿Por qué es tan difícil de resolver el problema?

Probar que P es igual a NP requiere un algoritmo rápido para un problema NP-completo, que nadie ha encontrado; probar que difieren requiere demostrar que tal algoritmo no puede existir. Los resultados sobre relativización y pruebas naturales demuestran que las técnicas estándar son inherentemente incapaces de establecer esto último, por lo que se necesita un enfoque genuinamente nuevo.