El problema P versus NP es un problema importante sin resolver en la informática teórica . En términos informales, plantea la pregunta de si todo problema cuya solución se puede verificar rápidamente también se puede resolver rápidamente.
Aquí, rápidamente significa que existe un algoritmo que resuelve la tarea y se ejecuta en tiempo polinomial , lo que significa que el tiempo de finalización de la tarea está limitado por una función polinomial en el tamaño de la entrada al algoritmo (en oposición a, digamos, el tiempo exponencial ). La clase general de preguntas que un algoritmo puede responder en tiempo polinomial es " P " o " clase P ". Para algunas preguntas, no se conoce una forma de encontrar una respuesta rápidamente, pero si se proporciona una respuesta, se puede verificar rápidamente. La clase de preguntas donde se puede verificar una respuesta en tiempo polinomial es NP , que significa "tiempo polinomial no determinista". [Nota 1]
Una respuesta a la pregunta P versus NP determinaría si los problemas que se pueden verificar en tiempo polinómico también se pueden resolver en tiempo polinómico. Si P ≠ NP, lo que se cree ampliamente, significaría que hay problemas en NP que son más difíciles de calcular que de verificar: no se podrían resolver en tiempo polinómico, pero la respuesta se podría verificar en tiempo polinómico.
El problema ha sido llamado el problema abierto más importante en la ciencia informática . [1] Además de ser un problema importante en la teoría computacional , una prueba en cualquier sentido tendría profundas implicaciones para las matemáticas, la criptografía , la investigación de algoritmos, la inteligencia artificial , la teoría de juegos , el procesamiento multimedia, la filosofía , la economía y muchos otros campos. [2]
Es uno de los siete Problemas del Premio del Milenio seleccionados por el Instituto de Matemáticas Clay , cada uno de los cuales conlleva un premio de US$1.000.000 para la primera solución correcta.
Considere el siguiente problema de sí/no: dada una cuadrícula de Sudoku incompleta de tamaño , ¿existe al menos una solución legal donde cada fila, columna y cuadrado contenga los números enteros del 1 al ? Es sencillo verificar instancias "sí" de este problema de Sudoku generalizado dada una solución candidata. Sin embargo, no se sabe si existe un algoritmo de tiempo polinomial que pueda responder correctamente "sí" o "no" a todas las instancias de este problema. Por lo tanto, el Sudoku generalizado está en NP (rápidamente verificable), pero puede o no estar en P (rápidamente solucionable). (Es necesario considerar una versión generalizada de Sudoku, ya que cualquier Sudoku de tamaño fijo tiene solo un número finito de cuadrículas posibles. En este caso, el problema está en P, ya que la respuesta se puede encontrar mediante una búsqueda en la tabla).
El enunciado preciso del problema P versus NP fue introducido en 1971 por Stephen Cook en su artículo seminal "La complejidad de los procedimientos de demostración de teoremas" [3] (e independientemente por Leonid Levin en 1973 [4] ).
Aunque el problema P versus NP se definió formalmente en 1971, ya existían indicios previos de los problemas involucrados, la dificultad de la prueba y las posibles consecuencias. En 1955, el matemático John Nash escribió una carta a la NSA , especulando que descifrar un código suficientemente complejo requeriría un tiempo exponencial en la longitud de la clave. [5] Si se demostraba (y Nash era adecuadamente escéptico), esto implicaría lo que ahora se llama P ≠ NP, ya que una clave propuesta puede verificarse en tiempo polinomial. Otra mención del problema subyacente ocurrió en una carta de 1956 escrita por Kurt Gödel a John von Neumann . Gödel preguntó si la demostración de teoremas (ahora conocida como co-NP-completa ) podría resolverse en tiempo cuadrático o lineal , [6] y señaló una de las consecuencias más importantes: que si era así, entonces el descubrimiento de pruebas matemáticas podría automatizarse.
La relación entre las clases de complejidad P y NP se estudia en la teoría de la complejidad computacional , la parte de la teoría de la computación que se ocupa de los recursos necesarios durante el cómputo para resolver un problema determinado. Los recursos más comunes son el tiempo (cuántos pasos se necesitan para resolver un problema) y el espacio (cuánta memoria se necesita para resolver un problema).
En este tipo de análisis, se requiere un modelo del ordenador cuyo tiempo se va a analizar. Normalmente, estos modelos suponen que el ordenador es determinista (dado el estado actual del ordenador y cualquier entrada, sólo hay una acción posible que el ordenador podría llevar a cabo) y secuencial (realiza acciones una tras otra).
En esta teoría, la clase P está formada por todos los problemas de decisión (definidos a continuación) que se pueden resolver en una máquina secuencial determinista en un polinomio de duración en el tamaño de la entrada; la clase NP está formada por todos los problemas de decisión cuyas soluciones positivas son verificables en tiempo polinomial dada la información correcta, o equivalentemente, cuya solución se puede encontrar en tiempo polinomial en una máquina no determinista . [7] Claramente, P ⊆ NP. Podría decirse que la mayor pregunta abierta en la informática teórica se refiere a la relación entre esas dos clases:
Desde 2002, William Gasarch ha realizado tres encuestas a investigadores sobre esta y otras cuestiones relacionadas. [8] [9] [10] La confianza en que P ≠ NP ha ido aumentando: en 2019, el 88% creía que P ≠ NP, frente al 83% en 2012 y el 61% en 2002. Cuando se restringió a los expertos, las respuestas de 2019 pasaron a ser el 99% que creía que P ≠ NP. [10] Estas encuestas no implican si P = NP, el propio Gasarch afirmó: "Esto no nos acerca a resolver P =? NP ni a saber cuándo se resolverá, pero intenta ser un informe objetivo sobre la opinión subjetiva de esta era".
Para abordar la cuestión P = NP, el concepto de NP-completitud es muy útil. Los problemas NP-completos son problemas a los que cualquier otro problema NP es reducible en tiempo polinómico y cuya solución sigue siendo verificable en tiempo polinómico. Es decir, cualquier problema NP puede transformarse en cualquier problema NP-completo. De manera informal, un problema NP-completo es un problema NP que es al menos tan "difícil" como cualquier otro problema en NP.
Los problemas NP-hard son aquellos que son al menos tan difíciles como los problemas NP; es decir, todos los problemas NP pueden reducirse (en tiempo polinomial) a ellos. Los problemas NP-hard no necesitan estar en tiempo polinomial; es decir, no necesitan tener soluciones verificables en tiempo polinomial.
Por ejemplo, el problema de satisfacibilidad booleano es NP-completo según el teorema de Cook-Levin , por lo que cualquier instancia de cualquier problema en NP se puede transformar mecánicamente en un problema de satisfacibilidad booleano en tiempo polinomial. El problema de satisfacibilidad booleano es uno de los muchos problemas NP-completos. Si cualquier problema NP-completo está en P, entonces se seguiría que P = NP. Sin embargo, muchos problemas importantes son NP-completos y no se conoce ningún algoritmo rápido para ninguno de ellos.
A partir de la definición por sí sola no es intuitivo que existan problemas NP-completos; sin embargo, un problema NP-completo trivial puede formularse de la siguiente manera: dada una máquina de Turing M garantizada para detenerse en tiempo polinomial, ¿existe una entrada de tamaño polinomial que M aceptará? [11] Está en NP porque (dada una entrada) es simple verificar si M acepta la entrada simulando M ; es NP-completo porque el verificador para cualquier instancia particular de un problema en NP puede codificarse como una máquina de tiempo polinomial M que toma la solución a verificar como entrada. Entonces la cuestión de si la instancia es una instancia de sí o no está determinada por si existe una entrada válida.
El primer problema natural que se demostró que era NP-completo fue el problema de satisfacibilidad booleano, también conocido como SAT. Como se señaló anteriormente, se trata del teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP-completo contiene detalles técnicos sobre las máquinas de Turing en relación con la definición de NP. Sin embargo, después de que se demostró que este problema era NP-completo, la prueba por reducción proporcionó una forma más sencilla de demostrar que muchos otros problemas también son NP-completos, incluido el juego Sudoku discutido anteriormente. En este caso, la prueba muestra que una solución de Sudoku en tiempo polinomial también podría usarse para completar cuadrados latinos en tiempo polinomial. [12] Esto, a su vez, proporciona una solución al problema de la partición de grafos tripartitos en triángulos, [13] que luego podría usarse para encontrar soluciones para el caso especial de SAT conocido como 3-SAT, [14] que luego proporciona una solución para la satisfacibilidad booleana general. De modo que una solución de un sudoku en tiempo polinómico conduce, mediante una serie de transformaciones mecánicas, a una solución de tiempo polinómico que es satisfacible, y que a su vez puede utilizarse para resolver cualquier otro problema NP en tiempo polinómico. Mediante transformaciones como ésta, una amplia clase de problemas aparentemente no relacionados se pueden reducir entre sí y, en cierto sentido, son "el mismo problema".
Aunque se desconoce si P = NP, se conocen problemas fuera de P. Así como la clase P se define en términos de tiempo de ejecución polinomial, la clase EXPTIME es el conjunto de todos los problemas de decisión que tienen tiempo de ejecución exponencial . En otras palabras, cualquier problema en EXPTIME se puede resolver mediante una máquina de Turing determinista en tiempo O (2 p ( n ) ), donde p ( n ) es una función polinomial de n . Un problema de decisión es EXPTIME-completo si está en EXPTIME, y cada problema en EXPTIME tiene una reducción de muchos a uno en tiempo polinomial . Se sabe que varios problemas son EXPTIME-completos. Debido a que se puede demostrar que P ≠ EXPTIME, estos problemas están fuera de P y, por lo tanto, requieren más que tiempo polinomial. De hecho, por el teorema de la jerarquía del tiempo , no se pueden resolver en un tiempo significativamente menor que el exponencial. Los ejemplos incluyen encontrar una estrategia perfecta para posiciones de ajedrez en un tablero N × N [15] y problemas similares para otros juegos de mesa. [16]
El problema de decidir la verdad de un enunciado en la aritmética de Presburger requiere incluso más tiempo. Fischer y Rabin demostraron en 1974 [17] que todo algoritmo que decide la verdad de enunciados de Presburger de longitud n tiene un tiempo de ejecución de al menos para alguna constante c . Por lo tanto, se sabe que el problema necesita más que un tiempo de ejecución exponencial. Aún más difíciles son los problemas indecidibles , como el problema de la parada . No pueden ser resueltos completamente por ningún algoritmo, en el sentido de que para cualquier algoritmo particular hay al menos una entrada para la cual ese algoritmo no producirá la respuesta correcta; o bien producirá la respuesta incorrecta, terminará sin dar una respuesta concluyente o, de lo contrario, se ejecutará eternamente sin producir ninguna respuesta en absoluto.
También es posible considerar otras cuestiones además de los problemas de decisión. Una de estas clases, que consiste en problemas de conteo, se llama #P : mientras que un problema NP pregunta "¿Hay soluciones?", el problema #P correspondiente pregunta "¿Cuántas soluciones hay?". Claramente, un problema #P debe ser al menos tan difícil como el problema NP correspondiente, ya que un recuento de soluciones indica inmediatamente si existe al menos una solución, si el recuento es mayor que cero. Sorprendentemente, algunos problemas #P que se cree que son difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal). [18] Para estos problemas, es muy fácil saber si existen soluciones, pero se piensa que es muy difícil saber cuántas. Muchos de estos problemas son #P-completos y, por lo tanto, se encuentran entre los problemas más difíciles en #P, ya que una solución en tiempo polinomial para cualquiera de ellos permitiría una solución en tiempo polinomial para todos los demás problemas #P.
En 1975, Richard E. Ladner demostró que si P ≠ NP, entonces existen problemas en NP que no están en P ni son NP-completos. [19] Dichos problemas se denominan problemas NP-intermedios. El problema del isomorfismo de grafos , el problema del logaritmo discreto y el problema de factorización de números enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas NP que no se sabe que estén en P o que sean NP-completos.
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos . Un importante problema sin resolver en la teoría de la complejidad es si el problema del isomorfismo de grafos está en P, NP-completo o NP-intermedio. La respuesta no se conoce, pero se cree que el problema al menos no es NP-completo. [20] Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. [21] Dado que se cree ampliamente que la jerarquía polinomial no colapsa a ningún nivel finito, se cree que el isomorfismo de grafos no es NP-completo. El mejor algoritmo para este problema, debido a László Babai , se ejecuta en tiempo cuasi-polinomial . [22]
El problema de factorización de enteros es el problema computacional de determinar la factorización prima de un entero dado. Expresado como un problema de decisión, es el problema de decidir si la entrada tiene un factor menor que k . No se conoce ningún algoritmo de factorización de enteros eficiente, y este hecho forma la base de varios sistemas criptográficos modernos, como el algoritmo RSA . El problema de factorización de enteros está en NP y en co-NP (e incluso en UP y co-UP [23] ). Si el problema es NP-completo, la jerarquía de tiempo polinomial colapsará a su primer nivel (es decir, NP = co-NP). El algoritmo conocido más eficiente para la factorización de enteros es el tamiz de campo numérico general , que toma el tiempo esperado
factorizar un entero de n bits. El algoritmo cuántico más conocido para este problema, el algoritmo de Shor , se ejecuta en tiempo polinomial, aunque esto no indica dónde radica el problema con respecto a las clases de complejidad no cuántica .
En todo el debate anterior se ha asumido que P significa "fácil" y que "no en P" significa "difícil", una suposición conocida como la tesis de Cobham . Es una suposición común en la teoría de la complejidad, pero hay salvedades.
En primer lugar, puede ser falso en la práctica. Un algoritmo polinomial teórico puede tener factores constantes o exponentes extremadamente grandes, lo que lo vuelve impráctico. Por ejemplo, el problema de decidir si un grafo G contiene a H como menor , donde H es fijo, se puede resolver en un tiempo de ejecución de O ( n 2 ), [25] donde n es el número de vértices en G . Sin embargo, la gran notación O esconde una constante que depende superexponencialmente de H . La constante es mayor que (usando la notación de flecha hacia arriba de Knuth ), y donde h es el número de vértices en H . [26]
Por otra parte, incluso si se demuestra que un problema es NP-completo, e incluso si P ≠ NP, todavía puede haber enfoques efectivos para el problema en la práctica. Hay algoritmos para muchos problemas NP-completos, como el problema de la mochila , el problema del viajante de comercio y el problema de satisfacibilidad booleana , que pueden resolver de manera óptima muchas instancias del mundo real en un tiempo razonable. La complejidad empírica del caso promedio (tiempo vs. tamaño del problema) de tales algoritmos puede ser sorprendentemente baja. Un ejemplo es el algoritmo simplex en programación lineal , que funciona sorprendentemente bien en la práctica; a pesar de tener una complejidad temporal exponencial en el peor de los casos , funciona a la par con los algoritmos de tiempo polinomial más conocidos. [27]
Por último, hay tipos de cálculos que no se ajustan al modelo de máquina de Turing en el que se definen P y NP, como la computación cuántica y los algoritmos aleatorios .
Cook ofrece una reformulación del problema en The P Versus NP Problem como "¿P = NP?" [28] Según las encuestas, [8] [29] la mayoría de los científicos informáticos creen que P ≠ NP. Una razón clave para esta creencia es que después de décadas de estudiar estos problemas nadie ha sido capaz de encontrar un algoritmo de tiempo polinomial para ninguno de los más de 3000 problemas NP-completos importantes conocidos (ver Lista de problemas NP-completos ). Estos algoritmos se buscaron mucho antes de que se definiera el concepto de NP-completitud ( los 21 problemas NP-completos de Karp , entre los primeros encontrados, eran todos problemas existentes bien conocidos en el momento en que se demostró que eran NP-completos). Además, el resultado P = NP implicaría muchos otros resultados sorprendentes que actualmente se cree que son falsos, como NP = co-NP y P = PH .
También se argumenta intuitivamente que la existencia de problemas que son difíciles de resolver pero cuyas soluciones son fáciles de verificar coincide con la experiencia del mundo real. [30]
Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que habitualmente suponemos. No habría ningún valor especial en los "saltos creativos", no habría ninguna brecha fundamental entre resolver un problema y reconocer la solución una vez encontrada.
Por otra parte, algunos investigadores creen que es demasiado confiado creer que P ≠ NP y que los investigadores también deberían explorar pruebas de P = NP. Por ejemplo, en 2002 se hicieron estas afirmaciones: [8]
El principal argumento a favor de P ≠ NP es la falta total de progreso fundamental en el área de búsqueda exhaustiva. Este es, en mi opinión, un argumento muy débil. El espacio de algoritmos es muy grande y estamos sólo al comienzo de su exploración. [...] La resolución del Último Teorema de Fermat también muestra que cuestiones muy simples sólo pueden resolverse mediante teorías muy profundas.
El apego a una especulación no es una buena guía para la planificación de una investigación. Siempre se deben intentar ambas direcciones de cada problema. El prejuicio ha hecho que matemáticos famosos no hayan podido resolver problemas famosos cuya solución era opuesta a sus expectativas, a pesar de que habían desarrollado todos los métodos necesarios.
Cuando se sustituye "tiempo lineal en una máquina de Turing multicinta" por "tiempo polinómico" en las definiciones de P y NP, se obtienen las clases DLIN y NLIN . Se sabe [31] que DLIN ≠ NLIN.
Una de las razones por las que el problema atrae tanta atención son las consecuencias de las posibles respuestas. Cualquiera de las dos direcciones de resolución haría avanzar enormemente la teoría y tal vez también tendría enormes consecuencias prácticas.
Una prueba de que P = NP podría tener consecuencias prácticas sorprendentes si la prueba conduce a métodos eficientes para resolver algunos de los problemas importantes en NP. Las posibles consecuencias, tanto positivas como negativas, surgen porque varios problemas NP-completos son fundamentales en muchos campos.
También es muy posible que una prueba no conduzca a algoritmos prácticos para problemas NP-completos. La formulación del problema no requiere que el polinomio acotado sea pequeño o incluso específicamente conocido. Una prueba no constructiva podría mostrar que existe una solución sin especificar ni un algoritmo para obtenerla ni un límite específico. Incluso si la prueba es constructiva, mostrando un polinomio acotado explícito y detalles algorítmicos, si el polinomio no es de orden muy bajo, el algoritmo podría no ser lo suficientemente eficiente en la práctica. En este caso, la prueba inicial sería principalmente de interés para los teóricos, pero el conocimiento de que son posibles las soluciones en tiempo polinomial seguramente estimularía la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.
Una solución que muestre que P = NP podría revolucionar el campo de la criptografía , que depende de que ciertos problemas sean difíciles. Una solución constructiva y eficiente [Nota 2] para un problema NP-completo como 3-SAT rompería la mayoría de los criptosistemas existentes, incluidos:
Estas necesitarían ser modificadas o reemplazadas con soluciones teóricamente seguras que no supongan P ≠ NP.
También se obtendrían enormes beneficios si se hicieran manejables muchos problemas que actualmente son matemáticamente intratables. Por ejemplo, muchos problemas en la investigación de operaciones son NP-completos, como los tipos de programación entera y el problema del viajante de comercio . La búsqueda de soluciones eficientes para estos problemas tendría enormes implicaciones para la logística. Muchos otros problemas importantes, como algunos problemas en la predicción de la estructura de las proteínas , también son NP-completos; [35] hacer que estos problemas se puedan resolver de manera eficiente podría hacer avanzar considerablemente las ciencias de la vida y la biotecnología.
Estos cambios podrían ser insignificantes comparados con la revolución que la resolución eficiente de problemas NP-completos causaría en las matemáticas mismas. Gödel, en sus primeras reflexiones sobre la complejidad computacional, señaló que un método mecánico que pudiera resolver cualquier problema revolucionaría las matemáticas: [36] [37]
Si realmente existiera una máquina con φ( n ) ∼ k ⋅ n (o incluso ∼ k ⋅ n 2 ), esto tendría consecuencias de la mayor importancia. Es decir, significaría obviamente que, a pesar de la indecidibilidad del Entscheidungsproblem , el trabajo mental de un matemático en relación con las preguntas de Sí o No podría ser reemplazado completamente por una máquina. Después de todo, uno simplemente tendría que elegir el número natural n tan grande que cuando la máquina no entregue un resultado, no tendría sentido pensar más en el problema.
De manera similar, Stephen Cook (suponiendo no sólo una prueba, sino un algoritmo prácticamente eficiente) dice: [28]
... transformaría las matemáticas al permitir que una computadora encuentre una prueba formal de cualquier teorema que tenga una prueba de una longitud razonable, ya que las pruebas formales pueden reconocerse fácilmente en tiempo polinomial. Los problemas de ejemplo pueden incluir todos los problemas del premio CMI .
Los matemáticos investigadores dedican su carrera a intentar demostrar teoremas, y algunas pruebas han tardado décadas o incluso siglos en encontrarse después de plantearse los problemas; por ejemplo, la prueba del último teorema de Fermat tardó más de tres siglos en demostrarse. Un método que garantizara la obtención de una prueba si existe una prueba de tamaño "razonable" pondría fin a esta lucha.
Donald Knuth ha declarado que ha llegado a creer que P = NP, pero tiene reservas sobre el impacto de una posible prueba: [38]
[...] si imaginamos un número M que es finito pero increíblemente grande —como, por ejemplo, el número 10↑↑↑↑3 del que hablé en mi artículo sobre "cómo lidiar con la finitud"— entonces hay una cantidad enorme de algoritmos posibles que realizan n M operaciones bit a bit o de adición o desplazamiento sobre n bits dados, y es realmente difícil creer que todos esos algoritmos fallen. Sin embargo, mi punto principal es que no creo que la igualdad P = NP resulte útil incluso si se demuestra, porque tal prueba casi seguramente no será constructiva.
Una prueba de P ≠ NP carecería de los beneficios computacionales prácticos de una prueba de P = NP, pero representaría un gran avance en la teoría de la complejidad computacional y guiaría la investigación futura. Demostraría que muchos problemas comunes no se pueden resolver de manera eficiente, de modo que la atención de los investigadores se puede centrar en soluciones parciales o soluciones a otros problemas. Debido a la creencia generalizada en P ≠ NP, gran parte de esta concentración de la investigación ya se ha producido. [39]
P ≠ NP aún deja abierta la complejidad del caso promedio de los problemas difíciles en NP. Por ejemplo, es posible que SAT requiera tiempo exponencial en el peor de los casos, pero que casi todas las instancias seleccionadas aleatoriamente de él sean eficientemente solucionables. Russell Impagliazzo ha descrito cinco "mundos" hipotéticos que podrían resultar de diferentes posibles resoluciones a la cuestión de la complejidad del caso promedio. [40] Estos van desde "Algorithmica", donde P = NP y problemas como SAT pueden resolverse eficientemente en todos los casos, hasta "Cryptomania", donde P ≠ NP y generar instancias difíciles de problemas fuera de P es fácil, con tres posibilidades intermedias que reflejan diferentes posibles distribuciones de dificultad sobre instancias de problemas NP-difíciles. El "mundo" donde P ≠ NP pero todos los problemas en NP son manejables en el caso promedio se llama "Heuristica" en el artículo. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos. [41]
Aunque el problema P = NP sigue abierto a pesar de un premio de un millón de dólares y una enorme cantidad de investigación dedicada, los esfuerzos para resolverlo han dado lugar a varias técnicas nuevas. En particular, algunas de las investigaciones más fructíferas relacionadas con el problema P = NP han demostrado que las técnicas de prueba existentes son insuficientes para responder a la pregunta, lo que sugiere que se requieren enfoques técnicos novedosos.
Como evidencia adicional de la dificultad del problema, esencialmente todas las técnicas de prueba conocidas en la teoría de la complejidad computacional caen en una de las siguientes clasificaciones, todas insuficientes para demostrar que P ≠ NP:
Estas barreras son otra razón por la que los problemas NP-completos son útiles: si se puede demostrar un algoritmo de tiempo polinomial para un problema NP-completo, esto resolvería el problema P = NP de una manera no excluida por los resultados anteriores.
Estas barreras llevan a algunos científicos informáticos a sugerir que el problema P versus NP puede ser independiente de los sistemas axiomáticos estándar como ZFC (no puede ser probado o refutado dentro de ellos). Un resultado de independencia podría implicar que P ≠ NP y esto es indemostrable en (por ejemplo) ZFC, o que P = NP pero es indemostrable en ZFC que cualquier algoritmo de tiempo polinomial sea correcto. [45] Sin embargo, si el problema es indecidible incluso con suposiciones mucho más débiles que extienden los axiomas de Peano para la aritmética de números enteros, entonces existen algoritmos de tiempo casi polinomial para todos los problemas NP. [46] Por lo tanto, asumiendo (como lo hacen la mayoría de los teóricos de la complejidad) que algunos problemas NP no tienen algoritmos eficientes, las pruebas de independencia con esas técnicas son imposibles. Esto también implica que probar la independencia de PA o ZFC con las técnicas actuales no es más fácil que probar que todos los problemas NP tienen algoritmos eficientes.
El problema P = NP puede reformularse como ciertas clases de enunciados lógicos, como resultado del trabajo en complejidad descriptiva .
Consideremos todos los lenguajes de estructuras finitas con una firma fija que incluya una relación de orden lineal . Entonces, todos esos lenguajes en P son expresables en lógica de primer orden con la adición de un combinador de punto fijo mínimo adecuado . Las funciones recursivas se pueden definir con esto y la relación de orden. Siempre que la firma contenga al menos un predicado o función además de la relación de orden distinguida, de modo que la cantidad de espacio que se toma para almacenar tales estructuras finitas sea en realidad polinomial en el número de elementos en la estructura, esto caracteriza precisamente a P.
De manera similar, NP es el conjunto de lenguajes expresables en lógica existencial de segundo orden —es decir, lógica de segundo orden restringida para excluir la cuantificación universal sobre relaciones, funciones y subconjuntos. Los lenguajes en la jerarquía polinómica , PH , corresponden a toda la lógica de segundo orden. Por lo tanto, la pregunta "¿es P un subconjunto propio de NP?" puede reformularse como "¿es la lógica existencial de segundo orden capaz de describir lenguajes (de estructuras finitas ordenadas linealmente con una firma no trivial) que la lógica de primer orden con el mínimo punto fijo no puede?". [47] La palabra "existencial" puede incluso eliminarse de la caracterización anterior, ya que P = NP si y solo si P = PH (ya que la primera establecería que NP = co-NP, lo que a su vez implica que NP = PH).
No se conoce ningún algoritmo para un problema NP-completo que se ejecute en tiempo polinomial. Sin embargo, existen algoritmos conocidos para problemas NP-completos que, si P = NP, se ejecutan en tiempo polinomial al aceptar instancias (aunque con constantes enormes, lo que hace que el algoritmo sea poco práctico). Sin embargo, estos algoritmos no se califican como de tiempo polinomial porque su tiempo de ejecución al rechazar instancias no es polinomial. El siguiente algoritmo, debido a Levin (sin ninguna cita), es un ejemplo de ello. Acepta correctamente el lenguaje NP-completo SUBSET-SUM . Se ejecuta en tiempo polinomial en entradas que están en SUBSET-SUM si y solo si P = NP:
// Algoritmo que acepta el lenguaje NP-completo SUBSET-SUM. // // este es un algoritmo de tiempo polinomial si y solo si P = NP. // // "Tiempo polinomial" significa que devuelve "sí" en tiempo polinomial cuando // la respuesta debería ser "sí", y se ejecuta para siempre cuando es "no". // // Entrada: S = un conjunto finito de enteros // Salida: "sí" si cualquier subconjunto de S suma 0. // Se ejecuta para siempre sin salida en caso contrario. // Nota: "Programa número M" es el programa obtenido al // escribir el entero M en binario, y luego // considerar esa cadena de bits como un // programa. Todos los programas posibles se pueden // generar de esta manera, aunque la mayoría no hace nada // debido a errores de sintaxis.PARA K = 1...∞ PARA M = 1...K Ejecute el programa número M durante K pasos con la entrada S SI el programa genera una lista de números enteros distintos Y los números enteros están todos en S Y los números enteros suman 0 ENTONCES SALIDA "sí" y DETENER
Este es un algoritmo de tiempo polinomial que acepta un lenguaje NP-completo solo si P = NP. "Aceptar" significa que da respuestas "sí" en tiempo polinomial, pero se le permite ejecutarse indefinidamente cuando la respuesta es "no" (también conocido como semialgoritmo ) .
Este algoritmo es enormemente impráctico, incluso si P = NP. Si el programa más corto que puede resolver SUBSET-SUM en tiempo polinomial tiene b bits de longitud, el algoritmo anterior probará al menos otros 2 b − 1 programas primero.
Un problema de decisión es un problema que toma como entrada una cadena w sobre un alfabeto Σ y da como salida "sí" o "no". Si hay un algoritmo (por ejemplo, una máquina de Turing o un programa informático con memoria ilimitada) que produce la respuesta correcta para cualquier cadena de entrada de longitud n en, como máximo , cn k pasos, donde k y c son constantes independientes de la cadena de entrada, entonces decimos que el problema se puede resolver en tiempo polinomial y lo colocamos en la clase P. Formalmente, P es el conjunto de lenguajes que se pueden resolver mediante una máquina de Turing determinista en tiempo polinomial. Es decir,
dónde
y una máquina de Turing de tiempo polinomial determinista es una máquina de Turing determinista M que satisface dos condiciones:
La NP se puede definir de manera similar utilizando máquinas de Turing no deterministas (la forma tradicional). Sin embargo, un enfoque moderno utiliza el concepto de certificado y verificador . Formalmente, la NP es el conjunto de lenguajes con un alfabeto finito y un verificador que se ejecuta en tiempo polinomial. A continuación se define un "verificador":
Sea L un lenguaje sobre un alfabeto finito, Σ.
L ∈ NP si, y sólo si, existe una relación binaria y un entero positivo k tales que se satisfacen las dos condiciones siguientes:
Una máquina de Turing que decide L R se llama verificador para L y un y tal que ( x , y ) ∈ R se llama certificado de membresía de x en L .
No todos los verificadores deben ser de tiempo polinómico. Sin embargo, para que L sea de tiempo polinómico, debe haber un verificador que se ejecute en tiempo polinómico.
Dejar
El hecho de que un valor de x sea compuesto es equivalente a que x sea miembro de COMPOSITE. Se puede demostrar que COMPOSITE ∈ NP verificando que satisface la definición anterior (si identificamos los números naturales con sus representaciones binarias).
Resulta que COMPOSITE también está en P, un hecho demostrado por la invención de la prueba de primalidad AKS . [48]
Hay muchas formas equivalentes de describir la NP-completitud.
Sea L un lenguaje sobre un alfabeto finito Σ.
L es NP-completo si, y sólo si, se cumplen las dos condiciones siguientes:
Alternativamente, si L ∈ NP, y hay otro problema NP-completo que puede reducirse en tiempo polinómico a L , entonces L es NP-completo. Esta es una forma común de demostrar que un nuevo problema es NP-completo.
Aunque el problema P versus NP generalmente se considera sin resolver, [49] muchos investigadores aficionados y algunos profesionales han afirmado tener soluciones. Gerhard J. Woeginger compiló una lista de 116 supuestas pruebas desde 1986 hasta 2016, de las cuales 61 eran pruebas de P = NP, 49 eran pruebas de P ≠ NP y 6 demostraban otros resultados, por ejemplo, que el problema es indecidible. [50] Algunos intentos de resolver P versus NP han recibido una breve atención de los medios, [51] aunque estos intentos han sido refutados.
La película Travelling Salesman , del director Timothy Lanzone, es la historia de cuatro matemáticos contratados por el gobierno de Estados Unidos para resolver el problema P versus NP. [52]
En el sexto episodio de la séptima temporada de Los Simpson , " Treehouse of Horror VI ", la ecuación P = NP se ve poco después de que Homer tropiece accidentalmente con la "tercera dimensión". [53] [54]
En el segundo episodio de la temporada 2 de Elementary , "Resolver para X", Sherlock y Watson investigan los asesinatos de matemáticos que intentaban resolver P versus NP. [55] [56]
Este problema se refiere a la cuestión de si las preguntas que son fáciles de verificar (una clase de consultas llamadas NP) también tienen soluciones que son fáciles de encontrar (una clase llamada P).
Supongamos que está organizando alojamiento para un grupo de cuatrocientos estudiantes universitarios. El espacio es limitado y solo cien de los estudiantes recibirán plazas en la residencia. Para complicar las cosas, el decano le ha proporcionado una lista de pares de estudiantes incompatibles y le ha solicitado que ningún par de esta lista aparezca en su elección final. Este es un ejemplo de lo que los informáticos llaman un problema NP...
