Hispanopedia Wiki
Articulo de referencia

Problema P versus NP

Problema sin resolver en informática Si la solución a un problema se puede comprobar en tiempo polinomial, ¿debe el problema ser resoluble en tiempo polinomial? Más problemas si...

Hispanopedia WikiContenido en espanolLectura gratuita
Problema sin resolver en informática
Si la solución a un problema se puede comprobar en tiempo polinomial, ¿debe el problema ser resoluble en tiempo polinomial?
Más problemas sin resolver en informática

El problema P versus NP es un importante problema sin resolver en la informática teórica . En términos informales, plantea la cuestión 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 (a diferencia de, por ejemplo, tiempo exponencial ), lo que significa que el tiempo de finalización de la tarea está acotado superiormente por una función polinomial del tamaño de la entrada del algoritmo. La clase general de preguntas que algún algoritmo puede responder en tiempo polinomial es " P " o "clase P". Para algunas preguntas, no se conoce ninguna forma de encontrar una respuesta rápidamente, pero si se proporciona una respuesta, se puede verificar rápidamente. La clase de preguntas cuya respuesta se puede verificar en tiempo polinomial es " NP ", que significa "tiempo polinomial no determinista". [ Nota 1 ] [ 1 ]

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 P  ≠  NP, como se cree comúnmente, significaría que existen problemas en NP que son más difíciles de calcular que de verificar: no podrían resolverse en tiempo polinomial, pero la respuesta sí podría verificarse en tiempo polinomial.

El problema ha sido considerado el problema abierto más importante en ciencias de la computación . [ 2 ] Además de ser un problema importante en teoría computacional , una demostración 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. [ 3 ] Es uno de los siete Problemas del Premio del Milenio seleccionados por el Instituto Clay de Matemáticas , cada uno de los cuales conlleva un premio de US$1,000,000 para la primera solución correcta.

Ejemplo

Considere el siguiente problema de sí/no: dada una cuadrícula de Sudoku incompleta de tamañonorte2×norte2{\displaystyle n^{2}\times n^{2}}¿Existe al menos una solución legal donde cada fila, columna ynorte×norte{\displaystyle n\times n}El cuadrado contiene los números enteros del 1 alnorte2{\displaystyle n^{2}}Es sencillo verificar las instancias "sí" de este problema de Sudoku generalizado dada una solución candidata. Sin embargo, se desconoce 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 pertenece a NP (verificable rápidamente), pero puede o no pertenecer a P (resoluble rápidamente). (Es necesario considerar una versión generalizada de Sudoku, ya que cualquier Sudoku de tamaño fijo solo tiene un número finito de cuadrículas posibles. En este caso, el problema pertenece a P, ya que la respuesta se puede encontrar mediante una tabla de búsqueda).

Historia

La formulación precisa del problema P versus NP fue introducida en 1971 por Stephen Cook en su artículo fundamental "La complejidad de los procedimientos de demostración de teoremas" [ 4 ] e independientemente por Leonid Levin en 1973. [ 5 ]

Aunque el problema P versus NP se definió formalmente en 1971, ya existían indicios previos de los problemas subyacentes. En 1955, el matemático John Nash escribió una carta a la Agencia de Seguridad Nacional , especulando que el tiempo necesario para descifrar un código suficientemente complejo aumentaría exponencialmente con la longitud de la clave. [ 6 ] De demostrarse, [ Nota 2 ] esto implicaría lo que ahora se denomina P  ≠  NP, ya que una clave propuesta puede verificarse en tiempo polinomial. 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 postuló que, de ser así, el descubrimiento de demostraciones matemáticas podría automatizarse. [ 7 ]

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 el cálculo 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 este tipo de 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 su estado actual y cualquier entrada, solo hay una acción posible que la computadora puede realizar) y secuencial (ejecuta las acciones una tras otra).

En esta teoría, la clase P consta de todos los problemas de decisión (definidos más adelante ) que se pueden resolver en una máquina secuencial determinista en un tiempo polinomial en el tamaño de la entrada; la clase NP consta de 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 . [ 8 ] Claramente, P ⊆ NP. Podría decirse que la mayor incógnita en la informática teórica se refiere a la relación entre estas dos clases:

¿Es P igual a NP?

Desde 2001, William Gasarch ha realizado tres encuestas a investigadores sobre P  ≠  NP y cuestiones relacionadas. [ 9 ] [ 10 ] [ 11 ] El porcentaje de encuestados que creían que P  ≠  NP fue del 61% en 2001, [ Nota 3 ] del 83% en 2011 y del 88% en 2018, con 100, 151 y 124 respuestas, respectivamente. [ 11 ] Al restringir la encuesta a expertos, el 99% de los encuestados en 2018 creían que P  ≠  NP. [ 11 ] Estas encuestas no implican si P  =  NP; como afirmó Gasarch: "Esto no nos acerca a resolver P=?NP ni a saber cuándo se resolverá, sino que intenta ser un informe objetivo sobre la opinión subjetiva de esta época". [ 9 ]

NP-completitud

Diagrama de Euler para los conjuntos de problemas P , NP , NP-completos y NP-difíciles (excluyendo el lenguaje vacío y su complemento, que pertenecen a P pero no son NP-completos).

Para abordar la cuestión de P  =  NP, el concepto de NP-completitud resulta muy útil. Los problemas NP-completos son aquellos a los que cualquier otro problema NP se puede reducir en tiempo polinomial y cuya solución sigue siendo verificable en tiempo polinomial. 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-difíciles 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-difíciles no necesariamente pertenecen a NP; es decir, no necesariamente tienen soluciones verificables en tiempo polinomial.

Por ejemplo, el problema de satisfacibilidad booleana 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 un problema de satisfacibilidad booleana en tiempo polinomial. El problema de satisfacibilidad booleana es uno de los muchos problemas NP-completos. Si algún problema NP-completo pertenece a P, entonces se deduce que P  =  NP. Sin embargo, muchos problemas importantes son NP-completos y no se conoce ningún algoritmo rápido para ninguno de ellos.

Por definición, 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 que garantiza detenerse en tiempo polinomial, ¿existe una entrada de tamaño polinomial que M acepte? [ 12 ] Es NP porque (dada una entrada) es sencillo comprobar 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 se determina por si existe una entrada válida.

El primer problema natural que se demostró que era NP-completo fue el problema de satisfacibilidad booleana, también conocido como SAT. Como se mencionó anteriormente, este es el teorema de Cook-Levin; su demostración 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 demostración por reducción proporcionó una forma más sencilla de demostrar que muchos otros problemas también son NP-completos, incluido el juego Sudoku que se analizó 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. [ 13 ] Esto a su vez da una solución al problema de particionar grafos tripartitos en triángulos, [ 14 ] que luego podría usarse para encontrar soluciones para el caso especial de SAT conocido como 3-SAT, [ 15 ] que luego proporciona una solución para la satisfacibilidad booleana general. Así, una solución polinomial para el Sudoku conduce, mediante una serie de transformaciones mecánicas, a una solución polinomial para la satisfacibilidad, la cual, a su vez, puede utilizarse para resolver cualquier otro problema NP en tiempo polinomial. Mediante transformaciones como esta, una vasta clase de problemas aparentemente no relacionados se reducen entre sí y, en cierto sentido, constituyen "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 tiempo de ejecución exponencial . En otras palabras, cualquier problema en EXPTIME puede ser resuelto por una máquina de Turing determinista en tiempo O (2p ( n ) ) , donde p ( n ) es una función polinomial de n . Un problema de decisión es EXPTIME-completo si está en EXPTIME, y todo problema en EXPTIME tiene una reducción de muchos a uno en tiempo polinomial . Se sabe que varios problemas son EXPTIME-completos. Dado 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, según el teorema de jerarquía temporal , no pueden resolverse en un tiempo significativamente menor que exponencial. Algunos ejemplos incluyen encontrar una estrategia perfecta para posiciones de ajedrez en un tablero N × N [ 16 ] y problemas similares para otros juegos de mesa. [ 17 ]

El problema de decidir la verdad de una proposición en la aritmética de Presburger requiere aún más tiempo. Fischer y Rabin demostraron en 1974 [ 18 ] que todo algoritmo que decide la verdad de proposiciones de Presburger de longitud n tiene un tiempo de ejecución de al menos22donorte{\displaystyle 2^{2^{cn}}}para alguna constante c . Por lo tanto, se sabe que el problema requiere un tiempo de ejecución mayor que el 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 bien se ejecutará indefinidamente 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 denomina #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 consideran difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal). [ 19 ] Para estos problemas, es muy fácil determinar si existen soluciones, pero se considera muy difícil determinar 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 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-completos

En 1975, Richard E. Ladner demostró que si P  ≠  NP, entonces existen problemas en NP que no pertenecen a P ni son NP-completos. [ 20 ] Estos problemas se denominan problemas NP-intermedios. El problema del isomorfismo de grafos , el problema del logaritmo discreto y el problema de la factorización de enteros son ejemplos de problemas que se consideran NP-intermedios. Son algunos de los pocos problemas NP que no se sabe que pertenezcan a P ni 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 del isomorfismo de grafos pertenece a P, es NP-completo o NP-intermedio. Se desconoce la respuesta, pero se cree que el problema al menos no es NP-completo. [ 21 ] Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial se reduce a su segundo nivel. [ 22 ] Dado que se cree ampliamente que la jerarquía polinomial no se reduce a ningún nivel finito, se considera que el isomorfismo de grafos no es NP-completo. El mejor algoritmo para este problema, desarrollado por László Babai , se ejecuta en tiempo cuasi-polinomial . [ 23 ]

El problema de factorización de enteros es el problema computacional de determinar la factorización prima de un entero dado. Formulado 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 constituye la base de varios sistemas criptográficos modernos, como el algoritmo RSA . El problema de factorización de enteros pertenece a NP y a co-NP (e incluso a UP y co-UP [ 24 ] ). 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 la criba de cuerpos numéricos general , que toma un tiempo esperado

O(exp⁡((64norte9registro⁡(2))13(registro⁡(norteregistro⁡(2)))23)){\displaystyle O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)}

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 se sitúa el problema con respecto a las clases de complejidad no cuántica .

Comparación de P con problemas "fáciles"

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

Toda la discusión anterior parte del supuesto de que P significa "fácil" y "no pertenece a P" significa "difícil", un supuesto conocido como la tesis de Cobham . Es un supuesto común en la teoría de la complejidad; sin embargo, existen 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 hace impracticable. Por ejemplo, el problema de decidir si un grafo G contiene a H como un menor , donde H es fijo, se puede resolver en un tiempo de ejecución de O ( n² ) , [ 26 ] donde n es el número de vértices en G. Sin embargo, la notación O grande oculta una constante que depende superexponencialmente de H. La constante es mayor que2↑ ↑(2↑ ↑(2↑ ↑(h/2))){\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}(utilizando la notación de flecha hacia arriba de Knuth ), y donde h es el número de vértices en H. [ 27 ]

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 el problema en la práctica. Existen algoritmos para muchos problemas NP-completos, como el problema de la mochila , el problema del viajante y el problema de satisfacibilidad booleana , que pueden resolver de forma óptima muchas instancias del mundo real en un tiempo razonable. La complejidad promedio empírica (tiempo vs. tamaño del problema) de dichos 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 , se ejecuta a la par con los mejores algoritmos conocidos de tiempo polinomial. [ 28 ]

Finalmente, existen tipos de computación que no se ajustan al modelo de máquina de Turing sobre el cual se definen P y NP, como la computación cuántica y los algoritmos aleatorios .

Razones para creer que P ≠ NP o P = NP

Cook proporciona una reformulación del problema en The P Versus NP Problem como "¿P  =  NP?" [ 29 ] Según las encuestas, [ 9 ] [ 30 ] la mayoría de los científicos de la computación 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 (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 creen falsos, como NP  = co-NP y P = PH .   

También se argumenta intuitivamente que la existencia de problemas difíciles de resolver pero cuyas soluciones son fáciles de verificar coincide con la experiencia del mundo real. [ 31 ]

Si P = NP, el mundo sería un lugar profundamente diferente al que solemos suponer. No habría ningún valor especial en los "saltos creativos", ni una brecha fundamental entre resolver un problema y reconocer la solución una vez encontrada.

Por otro lado, 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: [ 9 ]

El principal argumento a favor de P  ≠  NP es la total falta de progreso fundamental en el área de la búsqueda exhaustiva. En mi opinión, este es un argumento muy débil. El espacio de algoritmos es inmenso y apenas estamos comenzando a explorarlo. [...] La resolución del Último Teorema de Fermat también demuestra que cuestiones muy simples solo pueden resolverse mediante teorías muy profundas.

Aferrarse a una especulación no es una buena guía para planificar una investigación. Siempre se deben explorar ambas direcciones de cada problema. Los prejuicios han llevado a matemáticos famosos a fracasar en la resolución de problemas célebres cuya solución era contraria a sus expectativas, a pesar de haber desarrollado todos los métodos necesarios.

DLIN contra NLIN

Cuando se sustituye "tiempo lineal en una máquina de Turing de cintas múltiples" por "tiempo polinomial" en las definiciones de P y NP, se obtienen las clases DLIN y NLIN . Se sabe [ 32 ] que DLIN ≠ NLIN.

Consecuencias de la solución

Una de las razones por las que el problema atrae tanta atención son las consecuencias de las posibles soluciones. Cualquiera que sea la resolución, supondría un avance enorme para la teoría y, quizás, también tendría importantes consecuencias prácticas.

P = NP

Una demostración de que P  =  NP podría tener consecuencias prácticas sorprendentes si conduce a métodos eficientes para resolver algunos de los problemas importantes de NP. Las posibles consecuencias, tanto positivas como negativas, surgen dado que diversos 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 de acotación sea pequeño ni que se conozca específicamente. Una demostración no constructiva podría mostrar que existe una solución sin especificar ni un algoritmo para obtenerla ni una cota específica. Incluso si la demostración es constructiva, mostrando un polinomio de acotación explícito y detalles algorítmicos, si el polinomio no es de orden muy bajo, el algoritmo podría no ser 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 son posibles soluciones en tiempo polinomial sin duda impulsaría la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.

Una solución que demuestre que P  =  NP podría revolucionar el campo de la criptografía , que se basa en la dificultad de ciertos problemas. Una solución constructiva y eficiente [ Nota 4 ] a un problema NP-completo como 3-SAT rompería la mayoría de los criptosistemas existentes, incluyendo:

  • Las implementaciones existentes de criptografía de clave pública , [ 33 ] una base para muchas aplicaciones de seguridad modernas, como las transacciones financieras seguras a través de Internet.
  • Cifrados simétricos como AES o 3DES , [ 34 ] utilizados para el cifrado de datos de comunicaciones.
  • El hash criptográfico , que subyace a las criptomonedas blockchain como Bitcoin , se utiliza para autenticar las actualizaciones de software. Para estas aplicaciones, encontrar una preimagen que genere un hash con un valor dado debe ser difícil, idealmente con un tiempo exponencial. Si P = NP, entonces esto puede tomar un tiempo polinomial, mediante la reducción a SAT. [ 35 ]  

Estas soluciones necesitarían ser modificadas o reemplazadas por soluciones teóricamente seguras desde el punto de vista de la información que no asuman que P  ≠  NP.

También existen enormes beneficios que se derivarían de hacer abordables muchos problemas actualmente intratables matemáticamente. Por ejemplo, muchos problemas en investigación operativa son NP-completos, como ciertos 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 proteínas , también son NP-completos; [ 36 ] hacer que estos problemas sean resolubles de manera eficiente podría impulsar 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: [ 37 ] [ 38 ]

Si existiera una máquina con φ( n ) ∼ k ⋅ n (o incluso ∼ k ⋅ n² ) , esto tendría consecuencias de suma importancia. Es decir, implicaría que, a pesar de la indecidibilidad del problema de decisión , el trabajo mental de un matemático respecto a cuestiones de sí o no podría ser completamente reemplazado por una máquina. Al fin y al cabo, bastaría con elegir un número natural n tan grande que, cuando la máquina no arrojara un resultado, no tendría sentido seguir pensando en el problema.

De manera similar, Stephen Cook (suponiendo no solo una prueba, sino un algoritmo prácticamente eficiente) dice: [ 29 ]

...  transformaría las matemáticas al permitir que una computadora encuentre una demostración formal de cualquier teorema cuya demostración tenga una longitud razonable, ya que las demostraciones formales se pueden reconocer fácilmente en tiempo polinomial. Los ejemplos de problemas bien podrían incluir todos los problemas premiados por el CMI .

Los matemáticos investigadores dedican sus carreras a intentar demostrar teoremas, y algunas demostraciones han tardado décadas o incluso siglos en hallarse después de que se hayan planteado los problemas; por ejemplo, el Último Teorema de Fermat tardó más de tres siglos en demostrarse. Un método que garantice encontrar una demostración si existe una demostración de tamaño "razonable" pondría fin a esta lucha.

Donald Knuth ha declarado que ha llegado a creer que P  =  NP, pero se muestra reservado sobre el impacto de una posible demostración: [ 39 ]

[...] si imaginamos un número M finito pero increíblemente grande —como por ejemplo el número 10↑↑↑↑3 que se analiza 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, de suma o de 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 demostración casi con seguridad será no constructiva.

Diagrama de clases de complejidad siempre que P ≠ NP. La existencia de problemas dentro de NP pero fuera tanto de P como de NP-completos, bajo esa suposición, fue establecida por el teorema de Ladner . [ 20 ]  

P ≠ NP

Una demostración de P  ≠  NP carecería de las ventajas computacionales prácticas de una demostración de P  =  NP, pero representaría un gran avance en la teoría de la complejidad computacional y orientaría futuras investigaciones. Demostraría que muchos problemas comunes no pueden resolverse de manera eficiente, de modo que la atención de los investigadores podría centrarse en soluciones parciales o en soluciones a otros problemas. Debido a la creencia generalizada en P  ≠  NP, gran parte de esta reorientación de la investigación ya se ha producido. [ 40 ]

P  ≠  NP aún deja abierta la complejidad 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 aleatoriamente sean eficientemente resolubles. Russell Impagliazzo ha descrito cinco "mundos" hipotéticos que podrían resultar de diferentes posibles soluciones a la cuestión de la complejidad promedio. [ 41 ] Estos van desde "Algorithmica", donde P  =  NP y problemas como SAT pueden resolverse eficientemente 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 distribuciones posibles de dificultad sobre instancias de problemas NP-difíciles. El "mundo" donde P  ≠  NP pero todos los problemas en NP son tratables en el caso promedio se denomina "Heuristica" en el artículo. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos. [ 42 ]

Resultados sobre la dificultad de la prueba

Aunque el problema P  =  NP sigue abierto a pesar de un premio millonario y una gran cantidad de investigación dedicada a su resolución, los esfuerzos por 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 consistido en demostrar que las técnicas de demostración existentes son insuficientes para responder a la pregunta, lo que sugiere la necesidad de enfoques técnicos novedosos.

Como evidencia adicional de la dificultad del problema, prácticamente todas las técnicas de demostración conocidas en la teoría de la complejidad computacional se encuadran 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 probarse ni refutarse 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. [ 46 ] Sin embargo, si el problema es indecidible incluso con supuestos mucho más débiles que extienden los axiomas de Peano para la aritmética entera, entonces existen algoritmos de tiempo casi polinomial para todos los problemas NP. [ 47 ] Por lo tanto, asumiendo (como 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.

Caracterizaciones lógicas

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 signatura fija que incluya 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 . Con este combinador y la relación de orden, se pueden definir funciones recursivas. Siempre que la signatura contenga al menos un predicado o función, además de la relación de orden distinguida, de modo que el espacio necesario para almacenar dichas estructuras finitas sea polinomial en función del número de elementos de 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 linealmente ordenadas con signatura no trivial) que la lógica de primer orden con el menor punto fijo no puede?". [ 48 ] La palabra "existencial" puede incluso omitirse de la caracterización anterior, ya que P  =  NP si y solo si P  =  PH (ya que lo 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 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 los hace poco prácticos). No obstante, estos algoritmos no se consideran de tiempo polinomial porque su tiempo de ejecución al rechazar instancias no lo es. El siguiente algoritmo, de Levin (sin citar la fuente), es un ejemplo de ello. Acepta correctamente el lenguaje NP-completo SUBSET-SUM . Se ejecuta en tiempo polinomial con entradas que pertenecen a 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 indefinidamente cuando es "no". // // Entrada: S = un conjunto finito de enteros // Salida: "sí" si cualquier subconjunto de S suma 0. // Se ejecuta indefinidamente sin salida en caso contrario. // Nota: "Número de programa M" es el programa obtenido al // escribir el entero M en binario, y luego // considerar esa cadena de bits como un // programa. Cualquier programa posible puede ser // generado de esta manera, aunque la mayoría no hace nada // debido a errores de sintaxis. PARA K = 1...∞ PARA M = 1...K Ejecutar el programa número M durante K pasos con la entrada S SI el programa genera una lista de números enteros distintos Y todos los números enteros están en S Y la suma de los números enteros es 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 puede 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 intentará primero al menos 2b − 1 otros programas.

Definiciones formales

P y NP

Un problema de decisión es un problema que toma como entrada una cadena w sobre un alfabeto Σ y produce como salida "sí" o "no". Si existe 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 pueden ser decididos por una máquina de Turing determinista de tiempo polinomial. Es decir,

PAG={L:L=L(METRO) para alguna máquina de Turing determinista de tiempo polinomial METRO}{\displaystyle {\mathsf {P}}=\{L:L=L(M){\text{ para alguna máquina de Turing determinista de tiempo polinomial }}M\}}

dónde

L(METRO)={w∈Σ∗:METRO acepta w}{\displaystyle L(M)=\{w\in \Sigma ^{*}:M{\text{ acepta }}w\}}

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

  1. M se detiene en todas las entradas w y
  2. existek∈norte{\displaystyle k\in N}de tal manera queTMETRO(norte)∈O(nortek){\displaystyle T_{M}(n)\in O(n^{k})}, donde O se refiere a la notación de la gran O y
TMETRO(norte)=máximo{tMETRO(w):w∈Σ∗,|w|=norte}{\displaystyle T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}}
tMETRO(w)= número de pasos METRO tarda en detenerse al recibir una entrada. w.{\displaystyle t_{M}(w)={\text{ número de pasos }}M{\text{ tarda en detenerse con la entrada }}w.}

NP se puede definir de forma similar utilizando máquinas de Turing no deterministas (el método tradicional). Sin embargo, un enfoque moderno utiliza el concepto de certificado y verificador . Formalmente, 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 solo si, existe una relación binaria.R⊂Σ∗×Σ∗{\displaystyle R\subset \Sigma ^{*}\times \Sigma ^{*}}y un entero positivo k tal que se cumplan las dos condiciones siguientes:

  1. A pesar deincógnita∈Σ∗{\displaystyle x\in \Sigma ^{*}},incógnita∈L⇔∃y∈Σ∗{\displaystyle x\in L\Leftrightarrow \exists y\in \Sigma ^{*}}tal que ( x , y ) ∈ R y|y|∈O(|incógnita|k){\displaystyle |y|\in O(|x|^{k})}; y
  2. el idiomaLR={incógnita#y:(incógnita,y)∈R}{\displaystyle L_{R}=\{x\#y:(x,y)\in R\}}encimaΣ∪{#}{\displaystyle \Sigma \cup \{\#\}}es decidible por una máquina de Turing determinista en tiempo polinomial.

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 pertenencia de x en L .

No todos los verificadores tienen que ser de tiempo polinomial. Sin embargo, para que L pertenezca a NP, debe existir un verificador que se ejecute en tiempo polinomial.

Ejemplo

Dejar

doOMETROPAGOSITmi={incógnita∈norte∣incógnita=pagq para números enteros pag,q>1}{\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ para enteros }}p,q>1\right\}}
R={(incógnita,y)∈norte×norte∣1<y≤incógnita y y divide incógnita}.{\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ y }}y{\text{ divide }}x\right\}.}

Determinar si un valor de x es compuesto equivale a determinar si x pertenece a COMPOSITE. Se puede demostrar que COMPOSITE ∈ NP verificando que satisface la definición anterior (si identificamos los números naturales con sus representaciones binarias).

COMPOSITE también se encuentra en P, un hecho demostrado por la invención de la prueba de primalidad AKS . [ 49 ]

NP-completitud

Hay muchas maneras equivalentes de describir la NP-completitud.

Sea L un lenguaje 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 polinomial a L (escrito comoL′≤pagL{\displaystyle L'\leq _{p}L}), dóndeL′≤pagL{\displaystyle L'\leq _{p}L}Si, y solo si, se cumplen las dos condiciones siguientes:
    1. Existe f  : Σ* → Σ* tal que para todo w en Σ* se cumple:(w∈L′⇔F(w)∈L){\displaystyle (w\in L'\Leftrightarrow f(w)\in L)}; y
    2. Existe una máquina de Turing de tiempo polinomial que se detiene con f ( w ) en su cinta para cualquier entrada w .

Alternativamente, si L ∈ NP y existe otro problema NP-completo que puede reducirse a L en tiempo polinomial , entonces L es NP-completo. Esta es una forma común de demostrar que un nuevo problema es NP-completo.

Soluciones reclamadas

Aunque el problema P versus NP generalmente se considera sin resolver, [ 50 ] 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. [ 51 ] Algunos intentos de resolver P versus NP han recibido una breve atención mediática, [ 52 ] aunque estos intentos han sido refutados.

La película El viajante de comercio , del director Timothy Lanzone, cuenta la historia de cuatro matemáticos contratados por el gobierno de Estados Unidos para resolver el problema P versus NP. [ 53 ]

En el sexto episodio de la séptima temporada de Los Simpson , " La casa del terror VI ", la ecuación P = NP se ve poco después de que Homer tropiece accidentalmente con la "tercera dimensión". [ 54 ] [ 55 ]  

En el segundo episodio de la segunda temporada de Elementary , "Resolver para X", Holmes y Watson investigan los asesinatos de matemáticos que intentaban resolver P versus NP. [ 56 ] [ 57 ]

En el episodio " Pon tu cabeza sobre mis hombros " de la segunda temporada de la serie animada Futurama , aparece una referencia visual al problema P versus NP en el fondo. En una escena donde Fry y su compañera de trabajo Amy Wong se retiran a un armario de suministros para una conversación privada, detrás de ellos, en un estante junto a una caja etiquetada como "Frijoles de emergencia", hay dos libros del mismo tamaño, uno marcado como "P" y el otro como "NP". [ 58 ] [ 59 ]

Problemas similares

Véase también

Notas

  1. ↑ Una máquina de Turing no determinista puede transitar a un estado que no está determinado por el estado anterior. Dicha máquina podría resolver un problema NP en tiempo polinomial al llegar al estado de respuesta correcta (por casualidad) y luego verificarlo de forma convencional. Estas máquinas no son prácticas para resolver problemas reales, pero pueden utilizarse como modelos teóricos.
  2. ↑ Nash expresó su escepticismo sobre la posibilidad de que la conjetura se demostrara: "La naturaleza de esta conjetura es que no puedo demostrarla, ni siquiera para un tipo de cifrado sencillo. Ni espero que se demuestre".
  3. ↑ Las encuestas se realizaron en 2001, 2011 y 2018, pero se publicaron en 2002, 2012 y 2019 respectivamente. [ 11 ]
  4. ↑ El grado de eficiencia que debe tener una solución para representar una amenaza para la criptografía depende de los detalles. Una solución deO(norte2){\displaystyle O(N^{2})}con un término constante razonable sería desastroso. Por otro lado, una solución que seaΩ(norte4){\displaystyle \Omega (N^{4})}En casi todos los casos, no supondría un peligro práctico inmediato.

Referencias

  1. ↑ "Explicación: P vs. NP" . Noticias del MIT | Instituto Tecnológico de Massachusetts . 29 de octubre de 2009. Consultado el 6 de marzo de 2026 .
  2. ↑ Fortnow, Lance (2009). "El estado del problema P versus NP" (PDF) . Communications of the ACM . 52 (9): 78– 86. CiteSeerX 10.1.1.156.767 . doi : 10.1145/1562164.1562186 . S2CID 5969255. Archivado del original (PDF) el 24 de febrero de 2011. Recuperado el 26 de enero de 2010 .  
  3. ↑ Fortnow, Lance (2013). El billete dorado: P, NP y la búsqueda de lo imposible . Princeton, NJ: Princeton University Press. ISBN 9780691156491.
  4. ↑ Cook, Stephen (1971). «La complejidad de los procedimientos de demostración de teoremas» . Actas del Tercer Simposio Anual de la ACM sobre Teoría de la Computación . págs. 151–158 . doi : 10.1145/800157.805047 . ISBN  9781450374644. S2CID 7573663 . 
  5. ↑ Levin, LA (1973).Универсальные задачи перебора[ Problemas de Transmisión de Información ] . Problema. Передачи Информ (en ruso). 9 (3): 115-116 .
  6. ↑ NSA (2012). «Cartas de John Nash» (PDF) . Véanse las páginas 7-8. Archivado (PDF) del original el 9 de noviembre de 2018.{{cite web}}: CS1 mantenimiento: ubicación ( enlace )
  7. ↑ Hartmanis, Juris. "Gödel, von Neumann y el problema P = NP" (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica . 38 : 101–107 .
  8. ↑ Sipser, Michael: Introducción a la teoría de la computación, segunda edición, edición internacional , página 270. Thomson Course Technology, 2006. Definición 7.19 y teorema 7.20.
  9. 1 2 3 4 Gasarch, William I. (junio de 2002). "La encuesta P=?NP" ( PDF) . SIGACT News . 33 (2): 34– 47. CiteSeerX 10.1.1.172.1005 . doi : 10.1145/564585.564599 . S2CID 36828694. Archivado (PDF) del original el 15 de junio de 2007.  
  10. ↑ Gasarch, William I. " La segunda encuesta P=?NP" (PDF) . Noticias de SIGACT . 74. Archivado (PDF) del original el 24 de enero de 2014.
  11. 1 2 3 4 "Columna de invitados: La tercera encuesta P =? NP1" (PDF) . Archivado (PDF) del original el 31 de marzo de 2019. Recuperado el 25 de mayo de 2020 .
  12. ↑ Aaronson, Scott. "PHYS771 Lección 6: P, NP y amigos" . Consultado el 27 de agosto de 2007 .
  13. ↑ "Curso de maestría: Fundamentos de la informática" . www.cs.ox.ac.uk. Consultado el 25 de mayo de 2020 .
  14. ↑ Colbourn, Charles J. (1984). "La complejidad de completar cuadrados latinos parciales" . Matemáticas Aplicadas Discretas . 8 (1): 25– 30. doi : 10.1016/0166-218X(84)90075-1 .
  15. ↑ Holyer, I. (1981). "La NP-completitud de algunos problemas de partición de aristas". SIAM J. Comput . 10 (4): 713– 717. doi : 10.1137/0210054 .
  16. ↑ Fraenkel, Aviezri ; Lichtenstein, D. (1981). "Computing a perfect strategy for n × n chess requires time exponential in n ". Journal of Combinatorial Theory . Series A. 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 .
  17. ↑ Eppstein, David . "Complejidad computacional de juegos y rompecabezas" .
  18. ↑ Fischer, Michael J. ; Rabin, Michael O. (1974). "Complejidad superexponencial de la aritmética de Presburger" . Actas del Simposio SIAM-AMS de Matemáticas Aplicadas . 7 : 27–41 . Archivado del original el 15 de septiembre de 2006. Recuperado el 15 de octubre de 2017 .
  19. ↑ Valiant, Leslie G. (1979). "La complejidad de los problemas de enumeración y confiabilidad". SIAM Journal on Computing . 8 (3): 410– 421. doi : 10.1137/0208032 .
  20. 1 2 Ladner, RE (1975). "Sobre la estructura de la reducibilidad en tiempo polinomial" . Journal of the ACM . 22 : 151–171 Véase Corolario 1.1. doi : 10.1145/321864.321877 . S2CID 14352974 . 
  21. ↑ Arvind, Vikraman; Kurur, Piyush P. (2006). "El isomorfismo de grafos está en SPP". Information and Computation . 204 (5): 835– 852. doi : 10.1016/j.ic.2006.02.002 .
  22. ↑ Schöning, Uwe (1988). "El isomorfismo de grafos se encuentra en la jerarquía baja". Journal of Computer and System Sciences . 37 (3): 312– 323. doi : 10.1016/0022-0000(88)90010-4 .
  23. ↑ Babai, László (2018). "Grupo, grafos, algoritmos: el problema del isomorfismo de grafos". Actas del Congreso Internacional de Matemáticos—Río de Janeiro 2018. Vol. IV. Conferencias invitadas . World Sci. Publ., Hackensack, NJ. pp. 3319–3336 . MR 3966534 .  
  24. ↑ Lance Fortnow . Blog sobre complejidad computacional: Clase de complejidad de la semana: Factorización . 13 de septiembre de 2002.
  25. ↑ Pisinger, D. 2003. "¿Dónde están los problemas difíciles de la mochila?" Informe técnico 2003/08, Departamento de Informática, Universidad de Copenhague, Copenhague, Dinamarca
  26. ↑ Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (2012). "El problema de los caminos disjuntos en tiempo cuadrático" . Journal of Combinatorial Theory . Serie B. 102 (2): 424– 435. doi : 10.1016/j.jctb.2011.07.004 .
  27. ↑ Johnson, David S. (1987). "La columna de NP-completitud: una guía en curso (edición 19)". Journal of Algorithms . 8 (2): 285– 303. CiteSeerX 10.1.1.114.3864 . doi : 10.1016/0196-6774(87)90043-5 . 
  28. ↑ Gondzio, Jacek; Terlaky, Tamás (1996). "3 Una visión computacional de los métodos de punto interior" . En JE Beasley (ed.). Avances en programación lineal e entera . Oxford Lecture Series in Mathematics and its Applications. Vol. 4. Nueva York: Oxford University Press. pp. 103–144 . MR 1438311. Archivo Postscript en el sitio web de Gondzio y en el sitio web de Terlaky de la Universidad McMaster .   
  29. 1 2 Cook, Stephen (abril de 2000). "El problema P versus NP" (PDF) . Clay Mathematics Institute . Archivado (PDF) del original el 16 de diciembre de 2013. Recuperado el 18 de octubre de 2006 .
  30. ↑ Rosenberger, Jack (mayo de 2012). "Resultados de la encuesta P vs. NP" . Communications of the ACM . 55 (5): 10.
  31. ↑ Aaronson, Scott (4 de septiembre de 2006). "Razones para creer" ., punto 9.
  32. ↑ Balcázar, José Luis; Díaz, Josep; Gabarro, Joaquim (1990). Complejidad Estructural II . Springer Verlag. ISBN 3-540-52079-1., Teorema 3.9
  33. ↑ Véase Horie, S.; Watanabe, O. (1997). "Generación de instancias difíciles para SAT". Algorithms and Computation . Lecture Notes in Computer Science. Vol. 1350. Springer. pp. 22–31 . arXiv : cs/9809117 . Bibcode : 1998cs........9117H . doi : 10.1007/3-540-63890-3_4 . ISBN   978-3-540-63890-2.para una reducción de la factorización a SAT. Un problema de factorización de 512 bits (8400 años MIPS cuando se factoriza) se traduce en un problema SAT de 63.652 variables y 406.860 cláusulas.
  34. ↑ Véase, por ejemplo, Massacci, F.; Marraro, L. (2000). "Criptoanálisis lógico como problema SAT". Journal of Automated Reasoning . 24 (1): 165– 203. CiteSeerX 10.1.1.104.962 . doi : 10.1023/A:1006326723002 . S2CID 3114247 .  En el que una instancia de DES se codifica como un problema SAT con 10336 variables y 61935 cláusulas. Una instancia de problema 3DES tendría aproximadamente 3 veces este tamaño.
  35. ↑ De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Ataques de inversión a funciones hash seguras usando solucionadores SAT". Teoría y aplicaciones de las pruebas de satisfacibilidad – SAT 2007. Conferencia internacional sobre teoría y aplicaciones de las pruebas de satisfacibilidad. Springer. pp. 377–382 . doi : 10.1007/978-3-540-72788-0_36 .  
  36. ↑ Berger, B. ; Leighton, T. (1998). "El plegamiento de proteínas en el modelo hidrofóbico-hidrofílico (HP) es NP-completo". Journal of Computational Biology . 5 (1): 27– 40. CiteSeerX 10.1.1.139.5547 . doi : 10.1089/cmb.1998.5.27 . PMID 9541869 .  
  37. ↑ Historia de esta carta y su traducción de Sipser, Michael. "Historia y situación de la cuestión P versus NP" (PDF) . Archivado (PDF) del original el 2 de febrero de 2014.
  38. ↑ Johnson, David S. (agosto de 2012). «Una breve historia de la NP-completitud, 1954-2012». En Grötschel, M. (ed.). Optimization Stories (PDF) . Documenta Mathematica. págs. 359-376 . ISBN  978-3-936609-58-5ISSN 1431-0643​​ 
  39. ↑ Knuth, Donald E. (20 de mayo de 2014). Veinte preguntas para Donald Knuth . InformIT . Recuperado el 20 de julio de 2014 .
  40. ↑ Foulds, LR (octubre de 1983). "El enfoque heurístico para la resolución de problemas". Journal of the Operational Research Society . 34 (10): 927– 934. doi : 10.2307/2580891 . JSTOR 2580891 . 
  41. ↑ R. Impagliazzo, "Una visión personal de la complejidad del caso promedio" , pág. 134, 10.ª Conferencia Anual sobre Estructura en la Teoría de la Complejidad (SCT'95), 1995.
  42. ↑ "Programa tentativo para el taller sobre "Complejidad y criptografía: estado de los mundos de Impagliazzo"Archivado del original el 15 de noviembre de 2013.
  43. ↑ Baker, TP; Gill, J.; Solovay, R. (1975). "Relativizaciones de la pregunta NP P =?". SIAM Journal on Computing . 4 (4): 431– 442. doi : 10.1137/0204037 .
  44. ↑ Razborov, Alexander A.; Steven Rudich (1997). "Pruebas naturales" . Journal of Computer and System Sciences . 55 (1): 24– 35. doi : 10.1006/jcss.1997.1494 .
  45. 1 2 Aaronson, S.; Wigderson, A. (2008). Algebrización: una nueva barrera en la teoría de la complejidad (PDF) . Actas de ACM STOC'2008. págs. 731–740 . doi : 10.1145/1374376.1374481 . Archivado (PDF) del original el 21 de febrero de 2008. 
  46. ↑ Aaronson, Scott . "¿Son P y NP formalmente independientes?" (PDF) . Archivado (PDF) del original el 16 de enero de 2017..
  47. ↑ Ben-David, Shai; Halevi, Shai (1992). Sobre la independencia de P frente a NP . Technion (Informe técnico). Vol. 714. Archivado del original (GZIP) el 2 de marzo de 2012. .
  48. ↑ Elvira Mayordomo. "P versus NP" Archivado el 16 de febrero de 2012 en Wayback Machine Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
  49. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781– 793. doi : 10.4007/annals.2004.160.781 . JSTOR 3597229 . Archivado (PDF) desde el original el 26 de septiembre de 2006. 
  50. ↑ Markoff, John (8 de octubre de 2009). "Más allá de los premios, el rompecabezas P-NP tiene consecuencias" . The New York Times .
  51. ↑ Gerhard J. Woeginger . "La página P versus NP" . Consultado el 24 de junio de 2018 .
  52. ↑ Markoff, John (16 de agosto de 2010). "Paso 1: Publicar pruebas esquivas. Paso 2: Ver fuegos artificiales" . The New York Times . Consultado el 20 de septiembre de 2010 .
  53. ^ Geere, Duncan (26 de abril de 2012). "La película "El viajante" analiza las repercusiones si P es igual a NP . Wired UK . Consultado el 26 de abril de 2012 .
  54. ↑ Hardesty, Larry (29 de octubre de 2009). "Explicación: P vs. NP" .
  55. ↑ Shadia, Ajam (13 de septiembre de 2013). "¿Qué es el problema P vs. NP? ¿Por qué es importante?" .
  56. ↑ Gasarch, William (7 de octubre de 2013). "¿P vs NP es elemental? No, P vs NP es ON elemental" . blog.computationalcomplexity.org . Recuperado el 6 de julio de 2018 .
  57. ↑ Kirkpatrick, Noel (4 de octubre de 2013). "Reseña de Elementary Solve for X: Sines of Murder" . TV.com . Archivado del original el 7 de julio de 2018. Recuperado el 6 de julio de 2018 .
  58. ↑ Chris Loudon (director), Ken Keeler (guionista) (13 de febrero de 2000). "Pon tu cabeza sobre mis hombros". Futurama . Temporada 2. Episodio 7. Fox.
  59. ^ Georgoulias, Tom; Greenwald, Sarah J; Wichterich, Marc (2004). «Futurama πk Matemáticas en el año 3000» . Horizontes matemáticos . 11 (4): 12-15 .
  60. 1 2 Wigderson, Avi (2019). Matemáticas y computación: una teoría que revoluciona la tecnología y la ciencia . Princeton University Press. ISBN 978-0-691-18913-0.
  61. ↑ LG Valiant. Clases de completitud en álgebra. En Actas del 11.º ACM STOC, págs. 249–261, 1979.

Fuentes

  • Rachel Crowell (28 de mayo de 2021). "Las principales preguntas sin resolver en matemáticas siguen siendo en su mayoría misteriosas. Solo uno de los siete Problemas del Premio del Milenio nombrados hace 21 años ha sido resuelto" . www.scientificamerican.com . Consultado el 21 de junio de 2021. Este problema se refiere a la cuestión de si las preguntas que son fáciles de verificar (una clase de consultas llamada NP) también tienen soluciones que son fáciles de encontrar (una clase llamada P).
  • Hosch, William L (11 de agosto de 2009). "P versus NP problem mathematics" . Encyclopædia Britannica . Recuperado el 20 de junio de 2021 .
  • "Problema P vs NP" . www.claymath.org (Cook, Levin) . Archivado del original el 18 de junio de 2021. Consultado el 20 de junio de 2021. Supongamos que está organizando el alojamiento para un grupo de cuatrocientos estudiantes universitarios. El espacio es limitado y solo cien estudiantes obtendrán plaza en la residencia. Para complicar las cosas, el decano le ha proporcionado una lista de pares de estudiantes incompatibles y le ha pedido que ningún par de esta lista aparezca en su elección final. Este es un ejemplo de lo que los informáticos denominan un problema NP...

Lecturas adicionales

  • Fortnow, L.; Gasarch, W. "Complejidad computacional" .
  • La dificultad de la aproximación entre P y NP , de Aviad Rubinstein , fue galardonada con el Premio a la Mejor Tesis Doctoral de la ACM en 2017 .
  • "P vs. NP y el zoológico de la complejidad computacional" . 26 de agosto de 2014. Archivado del original el 24 de noviembre de 2021 – vía YouTube .
Lecturas relacionadas
6 articulos
{\displaystyle 2/{\sqrt {3}}}Lista de problemas sin resolver en informáticaEste artículo presenta una lista de problemas notables sin resolver en informática . Un problema en informática se considera sin resolver cuando no...Informática teóricaLa informática teórica es un subcampo de la informática y las matemáticas que se centra en los fundamentos abstractos y matemáticos de la computaci...Complejidad temporalComplejidad temporalEn informática teórica , la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que tarda un ordenador en ejecu...Complejidad temporalComplejidad temporalEn informática teórica , la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que tarda un ordenador en ejecu...Límites superior e inferiorLímites superior e inferiorEn matemáticas , particularmente en teoría del orden , un límite superior o mayor [1] de un subconjunto S de algún conjunto preordenado ( K , ≤) es...PolinomioPolinomioEn matemáticas , un polinomio es una expresión matemática que consta de indeterminados (también llamados variables ) y coeficientes , que involucra...