Problema P versus NP

El problema P versus NP es un importante problema sin resolver en informática teórica. En términos informales, pregunta si todos los problemas cuya solución puede verificarse rápidamente también pueden resolverse 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 (a diferencia de, digamos, el 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 le 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 pueden verificarse en tiempo polinomial también pueden resolverse en tiempo polinomial. Si resulta que P ≠ NP, como 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.

El problema ha sido llamado el problema abierto más importante en 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 del Milenio seleccionados por el Clay Mathematics Institute, cada uno de los cuales otorga un premio de 1 000 000 USD a 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 toman, 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 (rápidamente verificable) pero no parece estar en P (rápidamente solucionable). Miles de otros problemas parecen similares, en el sentido de 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 arrojado 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. Esto, sin embargo, nunca ha sido probado.

Historia

La declaración precisa del problema P versus NP fue presentada en 1971 por Stephen Cook en su artículo seminal "La complejidad de los procedimientos de prueba de teoremas" (e independientemente por Leonid Levin en 1973).

Aunque el problema de P versus NP se definió formalmente en 1971, hubo 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 en la que especulaba que descifrar un código lo suficientemente complejo requeriría un tiempo exponencial en la longitud de la clave. Si se prueba (y Nash se mostró adecuadamente escéptico), esto implicaría lo que ahora se llama P ≠ NP, ya que una clave propuesta se puede verificar 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 prueba de teoremas (que ahora se sabe que es co-NP-completa) podría resolverse en tiempo cuadrático o lineal, y señaló una de las consecuencias más importantes: de ser así, el descubrimiento de pruebas 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 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 tal análisis, se requiere un modelo de 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 consiste en todos aquellos problemas de decisión (definidos a continuación) que se pueden resolver en una máquina secuencial determinista en una cantidad de tiempo que es polinomial en el tamaño de la entrada; la clase NP consta de 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 de investigadores sobre esta y otras cuestiones relacionadas. La 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 restringió a expertos, las respuestas de 2019 se convirtieron en un 99 % que creían en P ≠ NP. Estas encuestas no implican nada sobre si P = NP es cierto, como afirma el propio Gasarch: "Esto no nos acerca más a resolver P=?NP ni a saber cuándo se resolverá, pero intenta ser un informe objetivo sobre la opinión subjetiva de esta época."

NP-completitud

Diagrama de Euler para P, NP, NP-complete y NP-hard conjunto de problemas (excluyendo el lenguaje vacío y su complemento, que pertenecen a P pero no son completos NP)

Para atacar la pregunta P = NP, el concepto de NP-completo es muy útil. Los problemas NP-completos son un conjunto de problemas a cada uno de los cuales cualquier otro problema NP puede reducirse en tiempo polinomial y cuya solución aún puede verificarse en tiempo polinomial. Es decir, cualquier problema NP puede transformarse en cualquiera de los problemas NP-completos. Informalmente, un problema NP-completo es un problema NP que es al menos igual de "difícil" como cualquier otro problema en NP.

Los problemas NP-difíciles son aquellos al menos tan difíciles como los problemas NP; es decir, todos los problemas NP se pueden reducir (en tiempo polinomial) 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 booleano de satisfacibilidad en tiempo polinomial. El problema de satisfacibilidad booleano es uno de los muchos problemas NP-completos de este tipo. 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 ningún algoritmo rápido para ninguno de ellos.

Basado solo 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 tiempo polinomial, ¿existe una entrada de tamaño polinomial que M aceptará? Está en NP porque (dada una entrada) es simple comprobar si M acepta la entrada simulando M; es NP-completo porque el verificador para cualquier instancia particular de un problema en NP se puede codificar como una máquina de tiempo polinomial M que toma la solución a verificar como entrada. Luego, 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 demostró ser 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 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 mostrar 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. Esto, a su vez, brinda una solución al problema de dividir gráficos tripartitos 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 Sudoku en tiempo polinomial conduce, mediante una serie de transformaciones mecánicas, a una solución de satisfacibilidad en tiempo polinomial, que a su vez puede usarse para resolver cualquier otro problema NP en tiempo polinomial. Usando transformaciones como esta, 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 tiempo O(2^p(n)), donde p(n) es una función polinómica de n. Un problema de decisión es EXPTIME-completo si está en EXPTIME, y cada problema en EXPTIME tiene una reducción polinomial de muchos a uno. Se sabe que varios problemas son EXPTIME-completo. Debido a que se puede demostrar que P ≠ EXPTIME, estos problemas están fuera de P y, por lo tanto, requieren más tiempo que el polinomial. De hecho, por 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 mesa.

El problema de decidir la verdad de una declaración en Presburger arithmetic requiere aún más tiempo. Fischer y Rabin probaron en 1974 que cada algoritmo que decide la verdad de las declaraciones de Presburger de longitud n tiene un tiempo de funcionamiento al menos ${displaystyle 2^{2^{cn}}$ para alguna constante c. Por lo tanto, se sabe que el problema necesita más que tiempo de ejecución exponencial. Aún más difícil son los problemas indecibles, como el problema de detener. No pueden ser completamente resueltos por cualquier algoritmo, en el sentido de que para cualquier algoritmo en particular hay por lo 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 ejecutar de otra manera para siempre sin producir ninguna respuesta en absoluto.

También es posible considerar otras cuestiones además de los problemas de decisión. Una de esas clases, que consiste en 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?" #34;. 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 consideran 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 decir 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.

Problemas en NP no conocidos por estar 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 factorización de 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 son NP-completos.

El problema de 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 gráficos 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. 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 polinomial no colapsa a ningún nivel finito, se cree que el isomorfismo del gráfico no es NP-completo. El mejor algoritmo para este problema, debido a László Babai, se ejecuta en tiempo cuasi-polinomio.

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 eficiente de factorización de enteros, 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). 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

${displaystyle Oleft(left({tfrac {64n}{9}log(2)right)^{frac {1}{3}}left(log(nlog(2))right)}{frac {2}{3}}right)}}right)}}}}}}right)}$

para factorizar un 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ánticas.

¿P significa "fácil"?

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

Toda la discusión anterior ha asumido 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 advertencias.

Primero, no siempre es verdad en la práctica. Un algoritmo polinomio teórico puede tener factores constantes extremadamente grandes o exponentes, lo que lo hace poco práctico. Por ejemplo, el problema de decidir si un gráfico G contiene H como menor, donde H se fija, se puede resolver en un tiempo de funcionamiento O()n²), 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 ${displaystyle 2uparrow uparrow (2uparrow uparrow (2uparrow uparrow (h/2))}$ (utilizando la notación de Knuth hacia arriba), 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, aún 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 empírica del caso promedio (tiempo frente al 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 polinomial más conocidos.

Finalmente, hay 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 aleatorios.

Razones para creer 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 importantes conocidos (consulte la 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 que se encontraron, 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 normalmente suponemos que es. No habría valor especial en "pasos creativos", ninguna brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentra.

—Scott Aaronson, UT Austin

Por otro lado, algunos investigadores creen que hay 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 sólo estamos al comienzo de su exploración. [...] La resolución del último teorema de Fermat también muestra que las preguntas muy simples pueden resolverse sólo por teorías muy profundas.

—Moshe Y. Vardi, Rice University

Estar unido a una especulación no es una buena guía para la planificación de la investigación. Uno siempre debe probar ambas direcciones de cada problema. Prejuicio ha causado que los matemáticos famosos no resuelvan problemas famosos cuya solución era contraria a sus expectativas, aunque habían desarrollado todos los métodos necesarios.

—Anil Nerode, Cornell University

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

P = NP

Una prueba de que P = NP podría tener impresionantes consecuencias prácticas 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 prueba no conduzca a algoritmos prácticos para problemas NP-completos. La formulación del problema no requiere que el polinomio acotante 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 prueba es constructiva y muestra un polinomio delimitador explícito y detalles algorítmicos, si el polinomio no es de orden muy bajo, es posible que el algoritmo no sea 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 las soluciones en tiempo polinomial son posibles seguramente estimularía la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.

Un ejemplo de un campo que podría verse alterado 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:

• Existen implementaciones de criptografía de clave pública, una base para muchas aplicaciones modernas de seguridad, como transacciones financieras seguras en Internet.
• Cifras simétricas como AES o 3DES, utilizadas para el cifrado de datos de comunicaciones.
• Cryptographic hashing, que subyace a criptomonedas de blockchain como Bitcoin, y se utiliza para autenticar actualizaciones de software. Para estas aplicaciones, el problema de encontrar una imagen previa que se apresura a un valor dado debe ser difícil para ser útil, y idealmente debe requerir tiempo exponencial. Sin embargo, si P = NP, entonces encontrar una imagen previa M se puede hacer en tiempo polinomio, a través de la reducción a SAT.

Deberían modificarse o reemplazarse por soluciones teóricamente seguras para la información que no se basen inherentemente en la inequivalencia P-NP.

Por otro lado, hay enormes consecuencias positivas que se derivarían de hacer manejables muchos problemas que actualmente son matemáticamente intratables. 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 de comercio. 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 proteínas, también son NP completos; si estos problemas se pudieran resolver de manera eficiente, podría 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-completos causaría en las propias matemáticas. 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²), esto tendría consecuencias de la mayor importancia. Es decir, obviamente significaría que a pesar de la indecisobilidad del Entscheidungsproblema, el trabajo mental de un matemático en relación con Yes-or-No las preguntas podrían ser reemplazadas 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 sobre el problema.

Del mismo modo, Stephen Cook (asumiendo no solo una prueba, sino un algoritmo prácticamente eficiente) dice:

... transformaría las matemáticas permitiendo a un ordenador encontrar una prueba formal de cualquier teorema que tiene una prueba de una longitud razonable, ya que las pruebas formales pueden ser fácilmente reconocidas en tiempo polinomio. Los problemas de ejemplo pueden incluir todos los problemas del premio CMI.

Los matemáticos investigadores 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 probarse. Un método que está garantizado para encontrar pruebas de teoremas, en caso de que exista un método "razonable" tamaño, esencialmente terminaría con esta lucha.

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

[...] si imaginas un número M que es finito pero increíblemente grande - como decir el número 10↑↑↑↑3 discutido en mi periódico en "copiar con finiteness" - entonces hay un número enorme de posibles algoritmos que hacen n^M bitwise o adición o operaciones de cambio en n dados pedazos, y es muy difícil creer que todos esos algoritmos fallan. Mi punto principal, sin embargo, es que no creo que la igualdad P = NP resulte ser útil incluso si se demuestra, porque tal 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 esa suposición, fue establecida por el teorema de Ladner.

P ≠ NP

Una prueba que muestra que P ≠ NP carecería de los beneficios computacionales prácticos de una prueba de que P = NP, pero que sin embargo representaría un avance muy significativo en la teoría de la complejidad computacional y proporcionaría orientación para futuras investigaciones. Permitiría mostrar de manera formal que muchos problemas comunes no se pueden resolver de manera eficiente, por lo que la atención de los investigadores puede enfocarse 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 aún deja abierta la complejidad del caso promedio de los 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ía resultar de diferentes resoluciones posibles a la cuestión de la complejidad del caso promedio. Estos van desde "Algorithmica", donde P = NP y problemas como SAT se pueden resolver de manera eficiente en todas las instancias, 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 en instancias de problemas NP-difíciles. El "mundo" donde P ≠ NP pero todos los problemas en NP son tratables en el caso promedio se llama "Heurística" en el papel. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos.

Resultados sobre dificultad de prueba

Aunque el problema P = NP sigue 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 mostrado que las técnicas de prueba existentes no son lo suficientemente poderosas para responder 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 se clasifican en una de las siguientes clasificaciones, cada una de las cuales se sabe que es insuficiente 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 también han llevado a algunos científicos informáticos a sugerir que el problema 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 prueba no se puede construir en (por ejemplo) ZFC, o que pueden existir algoritmos de tiempo polinomial para problemas NP-completos, pero es imposible probar en ZFC que tales algoritmos son correctos. Sin embargo, si se puede demostrar, utilizando técnicas del tipo que actualmente se sabe que son aplicables, que el problema no se puede resolver incluso con supuestos mucho más débiles que extiendan los axiomas de Peano (PA) para la aritmética de enteros, entonces necesariamente existiría casi polinomio -Algoritmos de tiempo para cada problema en NP. Por lo tanto, si uno cree (como lo 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 usando esas técnicas no pueden ser posibles. Además, este resultado implica que probar la independencia de PA o ZFC usando técnicas actualmente conocidas no es más fácil que probar 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 reclamado soluciones. Gerhard J. Woeginger compiló una lista de 62 supuestas pruebas de P = NP desde 1986 hasta 2016, de las cuales 50 eran pruebas de P ≠ NP, 2 eran pruebas de que el problema no es demostrable y una era una prueba de que es indecidible. 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 se puede reformular en términos de ciertas clases expresables de enunciados lógicos, como resultado del trabajo en la complejidad descriptiva.

Considere todos los lenguajes de estructuras finitas con una firma fija que incluya una relación de orden lineal. Entonces, todos esos lenguajes en P pueden expresarse 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 distinguida, de modo que la cantidad de espacio necesario para almacenar tales estructuras finitas sea en realidad un polinomio en el número de elementos de la estructura, esto caracteriza precisamente a P.

Del mismo modo, 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 de polinomios, 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 capaz la lógica existencial de segundo orden de describir lenguajes (de estructuras ordenadas linealmente finitas con firma no trivial) que la lógica de primer orden con punto fijo mínimo no puede?". La palabra "existencial" incluso puede eliminarse de la caracterización anterior, ya que P = NP si y solo si P = PH (ya que el primero 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, hay 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 en instancias de rechazo no es polinomial. El siguiente algoritmo, debido a Levin (sin ninguna cita), es un ejemplo de este tipo a continuación. 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 idioma NP-completo SUBSET-SUM.//// Este es un algoritmo de tiempo polinomio si y sólo si P = NP.//// "Polynomial-time" significa que vuelve "sí" en el tiempo polinomio cuando// la respuesta debe ser "sí", y corre para siempre cuando es "no".//// Entrada: S = un conjunto finito de enteros// Salida: "sí" si cualquier subconjunto de S agrega hasta 0.// Corre para siempre sin salida de otra manera.// Nota: "Número de programa M" es el programa obtenido por// escribir el entero M en binario, entonces// considerando esa cadena de bits para ser un// programa. Cada programa posible puede ser// generado de esta manera, aunque la mayoría no hacen nada// debido a errores de sintaxis.POR K = 1...
FOR M = 1...K
Ejecute el número de programa M para pasos K con entrada S
IF el programa produce una lista de enteros distintos
Y los enteros están todos en S
Y los enteros suma a 0
Entonces
"sí" y HALT

Si, y solo si, P = NP, entonces este es un algoritmo de tiempo polinomial que acepta un lenguaje NP completo. "Aceptando" significa que da "sí" responde en tiempo polinomial, pero puede ejecutarse indefinidamente cuando la respuesta es "no" (también conocido como semi-algoritmo).

Este algoritmo es enormemente poco prá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 intentará al menos 2^b − 1 otros programas primero.

Definiciones formales

P y NP

Conceptualmente hablando, un problema de decisión es un problema que toma como entrada una cadena w sobre un alfabeto Σ, y da como resultado "sí" o "no". Si hay un algoritmo (por ejemplo, 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, entonces decimos que el problema se puede resolver en polinomio tiempo 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 de tiempo polinomial determinista. Es decir,

${displaystyle mathbf {P} ={L:L=L(M){text{ for some deterministic polynomial-time Turing machine }}M}}$

dónde

${displaystyle L(M)={win ¿Qué?$

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

1. M paradas de todos los insumos w y
2. existe ${displaystyle kin N}$ tales que ${displaystyle T_{M}(n)in O(n^{k}$, donde O se refiere a la gran O notación y

${displaystyle ¿Qué?$

${displaystyle t_{M}(w)={text{ number of steps }M{text{ takes to halt on input }w.}$

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

Sea L una lengua sobre un alfabeto finito, Σ.

L zio NP si, y sólo si, existe una relación binaria ${displaystyle Rsubset Sigma ^{*}times Sigma ^{*}$ y un entero positivo k que las dos condiciones siguientes estén satisfechas:

1. Para todos ${displaystyle xin Sigma ^{*}$, ${displaystyle xin LLeftrightarrow exists yin Sigma ^{*}$ tal que (x, Sí.) R y ${displaystyle Silencioso 'in O(las vidas subidas)}$; y
2. el idioma ${displaystyle L_{R}={x#y:(x,y)in R}$ sobre ${displaystyle Sigma cup {#}}$ es decidable por una máquina de Turing determinista en tiempo polinomio.

Una máquina de Turing que decide L_R se denomina verificador para L y y tal que (x, y) ∈ R se denomina certificado de membresía de x en L.

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

Ejemplo

Dejar

${displaystyle mathrm {COMPOSITE} =left{xin mathbb {N} mid x=pq{text{ for integers }p,q confía1right}}}$

${displaystyle R=left{(x,y)in mathbb {N} times mathbb {N} mid 1 seleq {sqrt {x}{text{ and }y{ divides }xright}}}$

Claramente, la pregunta de si un x dado es un compuesto es equivalente a la pregunta de si x es un miembro de COMPOSITE. Se puede demostrar que COMPUESTO ∈ NP verificando que cumple la definición anterior (si identificamos los 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 la completitud de NP.

Sea L un lenguaje sobre un alfabeto finito Σ.

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

1. L zioDtTag
2. cualquiera L ' en NP es polinomial-time-reducible a L (escrito como ${displaystyle L'leq _{p}L}$), donde ${displaystyle L'leq _{p}L}$ si, y sólo si, las dos condiciones siguientes están satisfechas:
   1. Existe f:. w en la Asamblea* tenemos: ${displaystyle (win L'Leftrightarrow f(w)in L)}$; y
   2. existe una máquina de Turing polinomio-time 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 polinomial 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 los Estados Unidos para resolver el problema P versus NP.

En el sexto episodio de Los Simpson' séptima temporada " Treehouse of Horror VI", la ecuación P = NP se ve poco después de que Homer tropieza accidentalmente con la "tercera dimensión".

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