Problema de P versus NP - P versus NP problem

Problema no resuelto en informática :

Si la solución a un problema es fácil de verificar, ¿el problema debe ser fácil de resolver?

El problema de P versus NP es un problema importante sin resolver en la informática . Pregunta si todos los problemas cuya solución se puede verificar rápidamente también se pueden resolver rápidamente.

El término informal rápidamente , utilizado anteriormente, significa la existencia de un algoritmo que resuelve la tarea que se ejecuta en tiempo polinomial , de modo que el tiempo para completar la tarea varía como una función polinomial en el tamaño de la entrada al algoritmo (en oposición a, digamos, tiempo exponencial ). La clase general de preguntas para las que algún algoritmo puede proporcionar una respuesta en tiempo polinomial es " P " o " clase P ". Para algunas preguntas, no existe una forma conocida de encontrar una respuesta rápidamente, pero si se proporciona información que muestre cuál es la respuesta, es posible verificar la respuesta rápidamente. La clase de preguntas para las que se puede verificar una respuesta en tiempo polinomial es NP , que significa "tiempo polinomial no determinista".

Una respuesta a la pregunta P versus NP determinaría si los problemas que se pueden verificar en tiempo polinomial también se pueden resolver en tiempo polinomial. Si resulta que 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 podrían resolverse en tiempo polinomial, pero la respuesta podría verificarse en tiempo polinomial. .

Muchos consideran que el problema es el problema abierto más importante de la informática . Además de ser un problema importante en la teoría computacional , una prueba de cualquier manera 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.

Es uno de los siete problemas del premio Millennium seleccionados por el Clay Mathematics Institute , cada uno de los cuales lleva un premio de US $ 1.000.000 por la primera solución correcta.

Ejemplo

Considere el Sudoku , un juego en el que el jugador recibe una cuadrícula de números parcialmente completa e intenta completar la cuadrícula siguiendo ciertas reglas. Dada una cuadrícula de Sudoku incompleta, de cualquier tamaño, ¿existe al menos una solución legal? Cualquier solución propuesta se verifica fácilmente y el tiempo para verificar una solución crece lentamente (polinomialmente) a medida que la cuadrícula se hace más grande. Sin embargo, todos los algoritmos conocidos para encontrar soluciones requieren, para ejemplos difíciles, un tiempo que crece exponencialmente a medida que la cuadrícula se hace más grande. Entonces, Sudoku está en NP (se puede verificar rápidamente) pero no parece estar en P (se puede resolver rápidamente). Miles de otros problemas parecen similares, ya que son rápidos de comprobar pero lentos de resolver. Los investigadores han demostrado que muchos de los problemas en NP tienen la propiedad adicional de que una solución rápida a cualquiera de ellos podría usarse para construir una solución rápida a cualquier otro problema en NP, una propiedad llamada NP-completitud . Décadas de búsqueda no han producido una solución rápida a ninguno de estos problemas, por lo que la mayoría de los científicos sospechan que ninguno de estos problemas puede resolverse rápidamente. Sin embargo, esto nunca se ha probado.

Historia

El enunciado preciso del problema P versus NP fue introducido en 1971 por Stephen Cook en su artículo fundamental "La complejidad de los procedimientos de demostración de teoremas" (e independientemente por Leonid Levin en 1973).

Aunque el problema P versus NP se definió formalmente en 1971, había 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 , donde especuló que descifrar un código suficientemente complejo requeriría un tiempo exponencial en la longitud de la clave. Si se demuestra (y Nash era convenientemente escéptico), esto implicaría lo que ahora se llama P ≠ NP, ya que una clave propuesta puede verificarse fácilmente 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 , y señaló una de las consecuencias más importantes: que de ser así, entonces el descubrimiento de demostraciones matemáticas podría automatizarse.

Contexto

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 la computación para resolver un problema dado. 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 tal análisis, se requiere un modelo de la computadora para el cual se debe analizar el tiempo. Por lo general, estos modelos asumen que la computadora es determinista (dado el estado actual de la computadora y cualquier entrada, solo hay una acción posible que la computadora podría tomar) y secuencial (realiza acciones una tras otra).

En esta teoría, la clase P consta de todos aquellos problemas de decisión (definidos a continuación ) que pueden resolverse en una máquina secuencial determinista en una cantidad de tiempo que es polinomial en el tamaño de la entrada; la clase NP está formada por todos aquellos problemas de decisión cuyas soluciones positivas se pueden verificar 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 . 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:

¿Es P igual a NP?

Desde 2002, William Gasarch ha realizado tres encuestas a investigadores sobre esta y otras cuestiones relacionadas. Confianza en que P ≠ NP ha ido en aumento: en 2019, el 88% creía en P ≠ NP, en comparación con el 83% en 2012 y el 61% en 2002. Cuando se limita a los expertos, las respuestas de 2019 se convierten en 99% cree que P ≠ NP. Estas encuestas no implican nada sobre si P = NP es cierto, como afirma el propio Gasarch: ″ Esto no nos acerca a resolver P =? NP ni a saber cuándo se resolverá, pero intenta ser un objetivo informe sobre la opinión subjetiva de esta época ″.

NP-completitud

Diagrama de Euler para el conjunto de problemas P , NP , NP-completo y NP-difícil (excluyendo el lenguaje vacío y su complemento, que pertenecen a P pero no NP-completo)

Para atacar la pregunta P = NP, el concepto de NP-completitud es muy útil. Los problemas NP-completos son un conjunto de problemas a cada uno de los cuales se puede reducir cualquier otro problema NP en tiempo polinomial y cuya solución aún puede verificarse en tiempo polinomial. Es decir, cualquier problema de NP se puede transformar en cualquiera de los problemas de 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-difíciles son al menos tan difíciles como los problemas NP; es decir, todos los problemas de NP pueden reducirse (en tiempo polinómico) a ellos. Los problemas NP-difíciles no necesitan estar en NP; 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 puede transformarse mecánicamente en una instancia del problema de satisfacibilidad booleano en tiempo polinómico. El problema de satisfacibilidad booleano es uno de los muchos problemas NP completos. Si algún problema NP-completo está en P, entonces se seguiría que P = NP. Sin embargo, se ha demostrado que muchos problemas importantes son NP-completos y no se conoce un algoritmo rápido para ninguno de ellos.

Basándose únicamente en la definición, no es obvio que existan problemas NP-completos; sin embargo, un problema NP-completo trivial y artificial se puede formular de la siguiente manera: dada una descripción de una máquina de Turing M garantizada para detenerse en el tiempo polinomial, ¿existe una entrada de tamaño polinomial que M aceptará? Está en NP porque (dada una entrada) es sencillo comprobar si M acepta la entrada simulando M ; es NP-completo porque el verificador para cualquier caso particular de un problema en NP puede codificarse como una máquina M de tiempo polinomial que toma la solución para ser verificada como entrada. Entonces, la cuestión de si la instancia es 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, este es el teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP-completa contiene detalles técnicos sobre las máquinas de Turing en lo que respecta a la definición de NP. Sin embargo, después de que se probó que este problema era NP-completo, la prueba por reducción proporcionó una forma más sencilla de mostrar que muchos otros problemas también son NP-completos, incluido el juego Sudoku discutido anteriormente. En este caso, la demostración muestra que una solución de Sudoku en tiempo polinomial también podría usarse para completar cuadrados latinos en tiempo polinomial. Esto, a su vez, da una solución al problema de dividir gráficas tripartitas en triángulos, que luego podrían usarse para encontrar soluciones para el caso especial de SAT conocido como 3-SAT, que luego proporciona una solución para la satisfacibilidad booleana general. Entonces, una solución de tiempo polinomial para Sudoku conduce, mediante una serie de transformaciones mecánicas, a una solución de tiempo polinomial de satisfacibilidad, que a su vez puede usarse para resolver cualquier otro problema NP en tiempo polinomial. Utilizando transformaciones como ésta, una amplia clase de problemas aparentemente no relacionados son todos reducibles entre sí y, en cierto sentido, son "el mismo problema".

Problemas más difíciles

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 un tiempo de ejecución exponencial . En otras palabras, cualquier problema en EXPTIME se puede resolver mediante una máquina de Turing determinista en el tiempo O (2 p ( n ) ), donde p ( n ) es una función polinomial de n . Un problema de decisión es EXPTIME-complete si está en EXPTIME, y cada problema en EXPTIME tiene una reducción de varios uno en tiempo polinomial . Se sabe que varios problemas son EXPTIME-complete. Debido a que se puede demostrar que P ≠ EXPTIME, estos problemas están fuera de P y, por lo tanto, requieren más que un tiempo polinomial. De hecho, según el teorema de la jerarquía temporal , 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 y problemas similares para otros juegos de tablero.

El problema de decidir la verdad de un enunciado en la aritmética de Presburger requiere aún más tiempo. Fischer y Rabin demostraron en 1974 que cada algoritmo que decide la verdad de las declaraciones 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 detención . No pueden ser resueltos completamente por ningún algoritmo, en el sentido de que para cualquier algoritmo en particular hay al menos una entrada para la cual ese algoritmo no producirá la respuesta correcta; o producirá la respuesta incorrecta, terminará sin dar una respuesta concluyente o, de lo contrario, se ejecutará para siempre sin producir ninguna respuesta.

También es posible considerar cuestiones distintas de los problemas de decisión. Una de esas clases, que consta de problemas de conteo, se llama #P : mientras que un problema NP pregunta "¿Hay alguna solución?", 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 conteo de soluciones indica inmediatamente si existe al menos una solución, si el conteo 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). Para estos problemas, es muy fácil saber si existen soluciones, pero se cree que es muy difícil saber cuántas. Muchos de estos problemas son # P-completo y, por lo tanto, se encuentran entre los problemas más difíciles de #P, ya que una solución de tiempo polinomial para cualquiera de ellos permitiría una solución de tiempo polinomial para todos los demás problemas #P.

Problemas en NP que no se sabe que estén en P o NP-completo

En 1975, Richard E. Ladner demostró que si P ≠ NP entonces existen problemas en NP que no están ni en P ni en NP-completo. Estos problemas se denominan problemas NP intermedios. El problema del isomorfismo gráfico , el problema del logaritmo discreto y el problema de la factorización de enteros son ejemplos de problemas que se cree que son NP intermedios. Son algunos de los pocos problemas de 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 problema importante sin resolver en la teoría de la complejidad es si el problema de isomorfismo de grafos está en P, NP-completo o NP-intermedio. No se conoce la respuesta, pero se cree que el problema al menos no es NP-completo. Si el isomorfismo del gráfico es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. Dado que se cree ampliamente que la jerarquía de polinomios 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 .

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 constituye 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). Si el problema es NP-completo, la jerarquía de tiempo polinomial colapsará a su primer nivel (es decir, NP = co-NP). El algoritmo más conocido para la factorización de enteros es el tamiz de campo numérico general , que toma el tiempo esperado

para factorizar un número entero de n bits. Sin embargo, 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 .

¿P significa "fácil"?

El gráfico muestra el tiempo de ejecución frente al tamaño del problema para un problema de mochila de un algoritmo especializado de última generación. El ajuste cuadrático sugiere que la complejidad algorítmica del problema es O ((log ( n )) 2 ).

Toda la discusión anterior ha supuesto que P significa "fácil" y "no en P" significa "difícil", una suposición conocida como tesis de Cobham . Es una suposición común y razonablemente precisa en la teoría de la complejidad; sin embargo, tiene algunas salvedades.

Primero, no siempre es cierto en la práctica. Un algoritmo polinomial teórico puede tener factores constantes o exponentes extremadamente grandes, lo que lo vuelve poco práctico. Por ejemplo, el problema de decidir si un grafo G contiene H como un menor de edad , donde H es fijo, puede ser resuelto en un tiempo de ejecución de O ( n 2 ), donde n es el número de vértices en G . Sin embargo, la gran notación O esconde una constante que depende superexponentially en 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 .

Por otro lado, incluso si se demuestra que un problema es NP-completo, e incluso si P ≠ NP, todavía puede haber enfoques efectivos para abordar el problema en la práctica. Existen algoritmos para muchos problemas NP-completos, como el problema de la mochila , el problema del viajante de comercio y el problema de satisfacibilidad booleano , que pueden resolver de manera óptima muchas instancias del mundo real en un tiempo razonable. La complejidad de caso promedio empírico (tiempo versus 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 de tiempo exponencial en el peor de los casos , se ejecuta a la par con los algoritmos de tiempo polinómico más conocidos.

Por último, existen tipos de cálculos que no se ajustan al modelo de la máquina de Turing en el que se definen P y NP, como el cálculo cuántico y los algoritmos aleatorizados .

Razones para creer que P ≠ NP o P = NP

Cook proporciona una reformulación del problema en EL PROBLEMA P VERSUS NP como: ¿ P = NP ? . Según las encuestas, la mayoría de los 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 podido encontrar un algoritmo de tiempo polinomial para ninguno de los más de 3000 problemas NP-completos conocidos importantes (ver Lista de problemas NP-completos ). Estos algoritmos se buscaron mucho antes de que se definiera el concepto de NP-completo ( 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.

Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que solemos asumir. No habría ningún valor especial en los "saltos creativos", no habría una brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentra.

Por otro lado, algunos investigadores creen que existe un exceso de confianza en creer que P ≠ NP y que los investigadores también deberían explorar pruebas de P = NP. Por ejemplo, en 2002 se hicieron estas declaraciones:

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 los algoritmos es muy grande y solo estamos al comienzo de su exploración. [...] La resolución del último teorema de Fermat también muestra que las cuestiones muy simples sólo pueden resolverse mediante teorías muy profundas.

Estar apegado a una especulación no es una buena guía para la planificación de la investigación. Siempre se debe intentar en ambas direcciones de cada problema. El prejuicio ha provocado que matemáticos famosos no hayan podido resolver problemas famosos cuya solución era contraria a sus expectativas, a pesar de que habían desarrollado todos los métodos necesarios.

Consecuencias de la solución

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 la teoría enormemente y quizás también tendría enormes consecuencias prácticas.

P = NP

Una prueba de que P = NP podría tener consecuencias prácticas asombrosas 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 dado que varios problemas NP-completos son fundamentales en muchos campos.

También es muy posible que una demostración no conduzca a algoritmos prácticos para problemas NP-completos. La formulación del problema no requiere que el polinomio delimitador sea pequeño o incluso conocido específicamente. Una prueba no constructiva podría mostrar que existe una solución sin especificar un algoritmo para obtenerla o un límite específico. Incluso si la demostración es constructiva, mostrando un polinomio delimitador explícito y detalles algorítmicos, si el polinomio no es de muy bajo orden, el algoritmo podría no ser lo suficientemente eficiente en la práctica. En este caso, la demostración inicial sería de interés principalmente para los teóricos, pero el conocimiento de que las soluciones de tiempo polinomial son posibles sin duda estimularía la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.

Un ejemplo de un campo que podría ser desarraigado por una solución que muestre P = NP es la criptografía , que se basa en la dificultad de ciertos problemas. Una solución constructiva y eficiente a un problema NP-completo como 3-SAT rompería la mayoría de los criptosistemas existentes, incluidos:

  • Implementaciones existentes de criptografía de clave pública , una base para muchas aplicaciones de seguridad modernas, como transacciones financieras seguras a través de Internet.
  • Cifrados simétricos como AES o 3DES , utilizados para el cifrado de datos de comunicaciones.
  • Hash criptográfico , que subyace a las criptomonedas blockchain como Bitcoin , y se utiliza para autenticar actualizaciones de software. Para estas aplicaciones, el problema de encontrar una imagen previa que tenga un valor determinado debe ser difícil para que sea útil, e idealmente debería requerir un tiempo exponencial. Sin embargo, si P = NP, entonces la búsqueda de una imagen previa M se puede hacer en tiempo polinomial, mediante la reducción a SAT.

Estos tendrían que ser modificados o reemplazados por soluciones teóricamente seguras de la información que no se basen inherentemente en la desigualdad P-NP.

Por otro lado, hay enormes consecuencias positivas que se derivarían de hacer manejables muchos problemas matemáticamente insolubles en la actualidad. Por ejemplo, muchos problemas en la investigación de operaciones son NP-completos, como algunos tipos de programación entera y el problema del viajante . Las soluciones eficientes a estos problemas tendrían 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; si estos problemas pudieran resolverse de manera eficiente, podrían impulsar avances considerables en las ciencias de la vida y la biotecnología.

Pero tales cambios pueden palidecer en importancia en comparación con la revolución que un método eficiente para resolver problemas NP-completo causaría en las matemáticas mismas. Gödel, en sus primeros pensamientos sobre la complejidad computacional, señaló que un método mecánico que pudiera resolver cualquier problema revolucionaría las matemáticas:

Si realmente hubiera una máquina con φ (n) ∼ k ⋅ n (o incluso ∼ k ⋅ n 2 ), esto tendría consecuencias de la mayor importancia. Es decir, obviamente significaría que, a pesar de la indecidibilidad del Entscheidungsproblem , el trabajo mental de un matemático sobre preguntas de sí o no podría ser completamente reemplazado 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 entrega un resultado, no tiene sentido pensar más en el problema.

De manera similar, Stephen Cook (asumiendo no solo una prueba, sino un algoritmo prácticamente eficiente) dice

... 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 demostraciones formales pueden reconocerse fácilmente en tiempo polinomial. Los problemas de ejemplo pueden incluir todos los problemas de premios de CMI .

Los investigadores matemáticos pasan sus carreras tratando de probar teoremas, y algunas pruebas han tardado décadas o incluso siglos en encontrar después de que se han planteado los problemas; por ejemplo, el último teorema de Fermat tardó más de tres siglos en demostrarse. Un método que esté garantizado para encontrar pruebas de teoremas, si existiera uno de un tamaño "razonable", esencialmente terminaría con esta lucha.

Donald Knuth ha declarado que ha llegado a creer que P = NP, pero se reserva el impacto de una posible prueba:

[...] si imaginas un número M que es finito pero increíblemente grande, como el número 10 ↑↑↑↑ 3 discutido en mi artículo sobre "afrontar la finitud", entonces hay una enorme cantidad de algoritmos posibles que hacen n M bit a bit o operaciones de suma o desplazamiento en n bits dados, y es realmente difícil creer que todos esos algoritmos fallan. Mi punto principal, sin embargo, es que no creo que la igualdad P = NP resulte útil incluso si se prueba, porque esa prueba casi seguramente no será constructiva.

Diagrama de clases de complejidad siempre que P   NP. La existencia de problemas dentro de NP pero fuera de P y NP-completo, bajo ese supuesto, fue establecida por el teorema de Ladner .

P ≠ NP

Una prueba que mostró que P ≠ NP carecería de los beneficios computacionales prácticos de una prueba de que P = NP, pero sin embargo representaría un avance muy significativo en la teoría de la complejidad computacional y proporcionaría una guía para futuras investigaciones. Permitiría mostrar de manera formal que muchos problemas comunes no se pueden resolver de manera eficiente, de modo que la atención de los investigadores pueda centrarse en soluciones parciales o soluciones a otros problemas. Debido a la creencia generalizada en P ≠ NP, gran parte de este enfoque de la investigación ya se ha llevado a cabo.

Además, P ≠ NP todavía deja abierta la complejidad de casos promedio de problemas difíciles en NP. Por ejemplo, es posible que SAT requiera un tiempo exponencial en el peor de los casos, pero que casi todas las instancias seleccionadas al azar se puedan resolver de manera eficiente. Russell Impagliazzo ha descrito cinco "mundos" hipotéticos que podrían resultar de diferentes posibles resoluciones a la pregunta de complejidad del caso promedio. Estos van desde "Algorithmica", donde P = NP y problemas como SAT se pueden resolver de manera eficiente 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 casos de problemas NP-difíciles. El "mundo" donde P ≠ NP pero todos los problemas en NP son manejables en el caso promedio se llama "Heurística" en el documento. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos.

Resultados sobre la dificultad de la prueba

Aunque el problema P = NP en sí permanece abierto a pesar de un premio de un millón de dólares y una gran cantidad de investigación dedicada, los esfuerzos para resolver el problema han llevado 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 no son lo suficientemente poderosas 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, cada una de las cuales se sabe que es insuficiente para demostrar que P ≠ NP:

Clasificación Definición
Pruebas relativizantes Imagine un mundo en el que cada algoritmo puede realizar consultas a una subrutina fija llamada oráculo (una caja negra que puede responder a un conjunto fijo de preguntas en tiempo constante, como una caja negra que resuelve cualquier problema de viajante en un solo paso). , y el tiempo de ejecución del oráculo no se cuenta contra el tiempo de ejecución del algoritmo. La mayoría de las pruebas (especialmente las clásicas) se aplican uniformemente en un mundo con oráculos independientemente de lo que haga el oráculo. Estas pruebas se llaman relativizantes . En 1975, Baker, Gill y Solovay demostraron que P = NP con respecto a algunos oráculos, mientras que P ≠ NP para otros oráculos. Dado que las demostraciones de relativización solo pueden probar afirmaciones que son uniformemente verdaderas con respecto a todos los oráculos posibles, esto demostró que las técnicas de relativización no pueden resolver P = NP.
Pruebas naturales En 1993, Alexander Razborov y Steven Rudich definieron una clase general de técnicas de prueba para límites inferiores de complejidad de circuito, llamadas pruebas naturales . En ese momento, todos los límites inferiores del circuito conocidos anteriormente eran naturales, y la complejidad del circuito se consideró un enfoque muy prometedor para resolver P = NP. Sin embargo, Razborov y Rudich demostraron que, si existen funciones unidireccionales , ningún método de prueba natural puede distinguir entre P y NP. Aunque nunca se ha demostrado formalmente que existan funciones unidireccionales, la mayoría de los matemáticos creen que sí, y una prueba de su existencia sería una afirmación mucho más fuerte que P ≠ NP. Por lo tanto, es poco probable que las pruebas naturales por sí solas puedan resolver P = NP.
Pruebas de algebrización Después del resultado de Baker-Gill-Solovay, se utilizaron con éxito nuevas técnicas de prueba no relativizantes para demostrar que IP = PSPACE . Sin embargo, en 2008, Scott Aaronson y Avi Wigderson demostraron que la principal herramienta técnica utilizada en la prueba IP = PSPACE, conocida como aritmetización , también era insuficiente para resolver 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 también han llevado a algunos científicos informáticos a sugerir que el problema de P versus NP puede ser independiente de los sistemas de axiomas estándar como ZFC (no se puede probar ni refutar dentro de ellos). La interpretación de un resultado de independencia podría ser que no existe un algoritmo de tiempo polinomial para ningún problema NP-completo, y tal demostración no se puede construir en (por ejemplo) ZFC, o que pueden existir algoritmos de tiempo polinomial para problemas NP-completo, pero es imposible probar en ZFC que tales algoritmos sean correctos. Sin embargo, si se puede demostrar, utilizando técnicas del tipo que actualmente se sabe que son aplicables, que el problema no puede resolverse incluso con supuestos mucho más débiles que extienden los axiomas de Peano (PA) para aritmética de enteros, entonces necesariamente existiría casi- algoritmos de tiempo polinomial para cada problema en NP. Por lo tanto, si uno cree (como hacen la mayoría de los teóricos de la complejidad) que no todos los problemas en NP tienen algoritmos eficientes, se deduciría que las pruebas de independencia utilizando esas técnicas no pueden ser posibles. Además, este resultado implica que demostrar la independencia de PA o ZFC utilizando técnicas conocidas actualmente no es más fácil que demostrar la existencia de algoritmos eficientes para todos los problemas en NP.

Soluciones reclamadas

Si bien el problema de P versus NP generalmente se considera sin resolver, muchos investigadores aficionados y algunos profesionales han afirmado soluciones. Gerhard J. Woeginger mantiene una lista que, a partir de 2016, contiene 62 supuestas pruebas de P = NP, 50 pruebas de P ≠ NP, 2 pruebas de que el problema no se puede demostrar y una prueba de que es indecidible. Claramente, al menos 53 de estas pruebas están equivocadas. Algunos intentos de resolver P versus NP han recibido breve atención de los medios, aunque estos intentos han sido refutados desde entonces.

Caracterizaciones lógicas

El problema P = NP puede reformularse en términos de ciertas clases de enunciados lógicos expresables, como resultado del trabajo en complejidad descriptiva .

Considere todos los lenguajes de estructuras finitas con una firma fija que incluye una relación de orden lineal . Entonces, todos estos lenguajes en P se pueden expresar en lógica de primer orden con la adición de un combinador de punto fijo mínimo adecuado . Efectivamente, esto, en combinación con el orden, permite la definición de funciones recursivas. Siempre que la firma contenga al menos un predicado o función además de la relación de orden distinguido, de modo que la cantidad de espacio necesario para almacenar tales estructuras finitas sea en realidad polinomio en el número de elementos de la estructura, esto caracteriza precisamente a P.

De manera similar, NP es el conjunto de lenguajes que se pueden expresar en la lógica existencial de segundo orden , es decir, la lógica de segundo orden restringida para excluir la cuantificación universal sobre relaciones, funciones y subconjuntos. Los lenguajes de la jerarquía polinómica , PH , corresponden a toda la lógica de segundo orden. Por lo tanto, la pregunta "¿es P un subconjunto adecuado de NP" puede reformularse como "es la lógica existencial de segundo orden capaz de describir lenguajes (de estructuras finitas ordenadas linealmente con firma no trivial) que la lógica de primer orden con el mínimo punto fijo no puede?" . La palabra "existencial" se puede incluso quitar 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).

Algoritmos de tiempo polinomial

No se conoce ningún algoritmo para ningún problema NP-completo que se ejecute en tiempo polinomial. Sin embargo, existen algoritmos conocidos para problemas NP-completos con la propiedad de que si P = NP, entonces el algoritmo se ejecuta en tiempo polinomial al aceptar instancias (aunque con constantes enormes, lo que hace que el algoritmo no sea práctico). Sin embargo, estos algoritmos no califican como 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 a continuación. Acepta correctamente el lenguaje NP-complete SUBSET-SUM . Se ejecuta en tiempo polinomial en entradas que están en SUBSET-SUM si y solo si P = NP:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
//
// this is a polynomial-time algorithm if and only if P = NP.
//
// "Polynomial-time" means it returns "yes" in polynomial time when
// the answer should be "yes", and runs forever when it is "no".
//
// Input: S = a finite set of integers
// Output: "yes" if any subset of S adds up to 0.
// Runs forever with no output otherwise.
// Note: "Program number M" is the program obtained by
// writing the integer M in binary, then
// considering that string of bits to be a
// program. Every possible program can be
// generated this way, though most do nothing
// because of syntax errors.
FOR K = 1...∞
  FOR M = 1...K
    Run program number M for K steps with input S
    IF the program outputs a list of distinct integers
      AND the integers are all in S
      AND the integers sum to 0
    THEN
      OUTPUT "yes" and HALT

Si, y solo si, P = NP, entonces este es un algoritmo de tiempo polinomial que acepta un lenguaje NP-completo. "Aceptar" significa que da respuestas "sí" en tiempo polinomial, pero se permite que se ejecute 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 una longitud de b bits, el algoritmo anterior probará al menos 2 b - 1 otros programas primero.

Definiciones formales

P y NP

Hablando conceptualmente, un problema de decisión es un problema que toma como entrada alguna cadena w sobre un alfabeto Σ, y da como resultado "sí" o "no". Si hay un algoritmo (digamos una máquina de Turing o un programa de computadora con memoria ilimitada) que puede producir 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 , luego decimos que el problema se puede resolver en tiempo polinomial y lo ubicamos en la clase P. Formalmente, P se define como el conjunto de todos los lenguajes que pueden ser decididos por una máquina de Turing determinista de tiempo polinomial. Es decir,

dónde

y una máquina de Turing determinista de tiempo polinomial es una máquina de Turing determinista M que satisface las dos condiciones siguientes:

  1. M se detiene en todas las entradas W y
  2. existe tal que , donde O se refiere a la notación O grande y

NP se puede definir de manera similar utilizando máquinas de Turing no deterministas (la forma tradicional). Sin embargo, un enfoque moderno para definir NP es utilizar el concepto de certificado y verificador . Formalmente, NP se define como el conjunto de idiomas sobre un alfabeto finito que tienen un verificador que se ejecuta en tiempo polinomial, donde la noción de "verificador" se define de la siguiente manera.

Sea L una lengua sobre un alfabeto finito, Σ.

L ∈ NP si, y solo si, existe una relación binaria y un entero positivo k tal que se satisfacen las dos condiciones siguientes:

  1. Para todos , tal que ( x , y ) ∈ R y ; y
  2. el lenguaje más es decidible por una máquina de Turing determinista en tiempo polinómico.

La máquina A Turing que decide L R se llama un verificador de L y un y tal que ( x , y ) ∈ R se denomina un certificado de pertenencia de x en L .

En general, un verificador no tiene por qué ser de tiempo polinómico. Sin embargo, para que L esté en NP, debe haber un verificador que se ejecute en tiempo polinomial.

Ejemplo

Dejar

Claramente, la cuestión de si una x dada es un compuesto es equivalente a la cuestión de si x es un miembro de COMPOSITE. Se puede demostrar que COMPOSITE ∈ NP verificando que satisface la definición anterior (si identificamos números naturales con sus representaciones binarias).

COMPOSITE también está en P, un hecho demostrado por la invención de la prueba de primalidad AKS .

NP-completitud

Hay muchas formas equivalentes de describir NP-completitud.

Sea L una lengua sobre un alfabeto finito Σ.

L es NP-completo si, y solo si, se cumplen las dos condiciones siguientes:

  1. L ∈ NP; y
  2. cualquier L en NP es reducible en tiempo polinómico a L (escrito como ), donde si, y solo si, se cumplen las dos condiciones siguientes:
    1. Existe f  : Σ → Σ * * tal que para todo w en Σ * tenemos: ; y
    2. existe una máquina de Turing de tiempo polinomial que se detiene con f ( w ) en su cinta en cualquier entrada w .

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 probar que algún problema nuevo es NP-completo.

Cultura popular

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.

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 accidentalmente se topa con la "tercera dimensión".

En el segundo episodio de la temporada 2 de Elementary , "Resuelve para X" gira en torno a Sherlock y Watson que investigan los asesinatos de matemáticos que intentaban resolver P contra NP.

Ver también

Notas

Referencias

Fuentes

Otras lecturas

enlaces externos