Si la solución a un problema es fácil de verificar, ¿el problema debe ser fácil de resolver?
El problema de P versus NP es un problema importante sin resolver en la informática . Pregunta si todos los problemas cuya solución se puede verificar rápidamente también se pueden resolver rápidamente.
Es uno de los siete problemas del premio Millennium seleccionados por el Clay Mathematics Institute , cada uno de los cuales lleva un premio de US $ 1.000.000 por la primera solución correcta.
El término informal rápidamente , usado anteriormente, significa la existencia de un algoritmo que resuelve la tarea que se ejecuta en tiempo polinomial , de modo que el tiempo para completar la tarea varía como una función polinomial en el tamaño de la entrada al algoritmo (en contraposición a, digamos, tiempo exponencial ). La clase general de preguntas para las que algún algoritmo puede proporcionar una respuesta en tiempo polinomial se llama "clase P " o simplemente " P ". Para algunas preguntas, no existe una forma conocida de encontrar una respuesta rápidamente, pero si se proporciona información que muestre cuál es la respuesta, es posible verificar la respuesta rápidamente. La clase de preguntas para las que se puede verificar una respuesta en tiempo polinomial se llama NP , que significa "tiempo polinomial no determinista". [Nota 1]
Una respuesta a la pregunta P versus NP determinaría si los problemas que se pueden verificar en tiempo polinomial también se pueden resolver en tiempo polinomial. Si resultara que P ≠ NP , que es ampliamente creído, significaría que hay problemas en NP que son más difíciles de calcular que de verificar: no se podrían resolver en tiempo polinomial, pero la respuesta se podría verificar en tiempo polinomial. .
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. [2]
Ejemplo
Considere el Sudoku , un juego en el que el jugador recibe una cuadrícula de números parcialmente completa e intenta completar la cuadrícula siguiendo ciertas reglas. Dada una cuadrícula de Sudoku incompleta, de cualquier tamaño, ¿existe al menos una solución legal? Cualquier solución propuesta se verifica fácilmente y el tiempo para verificar una solución crece lentamente (polinomialmente) a medida que la cuadrícula se hace más grande. Sin embargo, todos los algoritmos conocidos para encontrar soluciones requieren, para ejemplos difíciles, un tiempo que crece exponencialmente a medida que la cuadrícula se hace más grande. Entonces, Sudoku está en NP (se puede verificar rápidamente) pero no parece estar en P (se puede resolver rápidamente). Miles de otros problemas parecen similares, ya que son rápidos de comprobar pero lentos de resolver. Los investigadores han demostrado que muchos de los problemas en NP tienen la propiedad adicional de que una solución rápida a cualquiera de ellos podría usarse para construir una solución rápida a cualquier otro problema en NP , una propiedad llamada NP -completitud . Décadas de búsqueda no han producido una solución rápida a ninguno de estos problemas, por lo que la mayoría de los científicos sospechan que ninguno de estos problemas puede resolverse rápidamente. Sin embargo, esto nunca se ha probado.
Historia
El enunciado preciso del problema P versus NP fue introducido en 1971 por Stephen Cook en su artículo seminal "La complejidad de los procedimientos de demostración de teoremas" [3] (e independientemente por Leonid Levin en 1973 [4] ) y muchos lo consideran el problema abierto más importante de la informática . [5]
Aunque el problema P versus NP se definió formalmente en 1971, había indicios previos de los problemas involucrados, la dificultad de la prueba y las posibles consecuencias. En 1955, el matemático John Nash escribió una carta a la NSA , donde especuló que descifrar un código suficientemente complejo requeriría un tiempo exponencial en la longitud de la clave. [6] Si se demuestra (y Nash era convenientemente 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 demostración de teoremas (ahora conocida como co-NP -completa ) podría resolverse en tiempo cuadrático o lineal , [7] y señaló una de las consecuencias más importantes: que, de ser así, entonces el descubrimiento de demostraciones matemáticas podría ser automatizado.
Contexto
La relación entre las clases de complejidad P y NP se estudia en la teoría de la complejidad computacional , la parte de la teoría de la computación que se ocupa de los recursos necesarios durante la computación para resolver un problema dado. Los recursos más comunes son el tiempo (cuántos pasos se necesitan para resolver un problema) y el espacio (cuánta memoria se necesita para resolver un problema).
En tal análisis, se requiere un modelo de la computadora para el cual se debe analizar el tiempo. Por lo general, estos modelos asumen que la computadora es determinista (dado el estado actual de la computadora y cualquier entrada, solo hay una acción posible que la computadora podría tomar) y secuencial (realiza acciones una tras otra).
En esta teoría, la clase P consta de todos aquellos problemas de decisión (definidos a continuación ) que 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 está formada por todos aquellos problemas de decisión cuyas soluciones positivas se pueden verificar en tiempo polinomial dada la información correcta, o equivalentemente, cuya solución se puede encontrar en tiempo polinomial en una máquina no determinista . [8] Claramente, P ⊆ NP . Podría decirse que la mayor pregunta abierta en la informática teórica se refiere a la relación entre esas dos clases:
- ¿Es P igual a NP ?
Desde 2002, William Gasarch ha realizado tres encuestas a investigadores sobre esta y otras cuestiones relacionadas. [9] [10] [11] Confianza en que P ≠ NP ha ido en aumento: en 2019, el 88% creía que P ≠ NP , frente al 83% en 2012 y el 61% en 2002. Cuando se limita a los expertos, las respuestas de 2019 se convirtieron en El 99% cree que P ≠ NP . [11] Estas encuestas no implican nada sobre si P = NP es cierto, como afirma el propio Gasarch: ″ Esto no nos acerca a resolver P =? NP o saber cuándo se resolverá, pero pretende ser un informe objetivo sobre la opinión subjetiva de esta época ″.
NP-completitud
Para atacar la pregunta P = NP , el concepto de NP -completo es muy útil. Los problemas NP- completos son un conjunto de problemas para 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. De manera informal, un problema NP- completo es un problema NP que es al menos tan "difícil" como cualquier otro problema en NP .
Los problemas NP- difíciles son al menos tan difíciles como losproblemas NP ; es decir, todos losproblemas de NP pueden reducirse (en tiempo polinómico) a ellos. NP : no es necesario que los problemas difíciles estén en NP ; es decir, no necesitan tener soluciones verificables en tiempo polinomial.
Por ejemplo, el problema de satisfacibilidad booleano es NP -completo según el teorema de Cook-Levin , por lo que cualquier instancia de cualquier problema en NP puede transformarse mecánicamente en una instancia del problema de satisfacibilidad booleano en tiempo polinómico. El problema de satisfacibilidad booleano es uno de los muchos problemas NP completos. Si algún problema NP- completo está en P , entonces se seguiría que P = NP . Sin embargo, se ha demostrado que muchos problemas importantes son NP- completos, y no se conoce un algoritmo rápido para ninguno de ellos.
Basándose únicamente en la definición, no es obvio que existan problemas NP- completos; sin embargo, un problema NP- completo trivial y artificial se puede formular de la siguiente manera: dada una descripción de una máquina de Turing M garantizada para detenerse en el tiempo polinomial, ¿existe una entrada de tamaño polinomial que M aceptará? [12] Está en NP porque (dada una entrada) es sencillo comprobar si M acepta la entrada simulando M ; es NP -completo porque el verificador para cualquier caso particular de un problema en NP puede codificarse como una máquina de tiempo polinomial M que toma la solución para ser verificada como entrada. Entonces, la cuestión de si la instancia es sí o no está determinada por si existe una entrada válida.
El primer problema natural que se demostró que era NP- completo fue el problema de satisfacibilidad booleano, también conocido como SAT. Como se señaló anteriormente, este es el teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP -completa contiene detalles técnicos sobre las máquinas de Turing en lo que respecta a la definición de NP . Sin embargo, después de que se probó que este problema era NP -completo, la prueba por reducción proporcionó una forma más sencilla de mostrar que muchos otros problemas también son NP -completos, incluido el juego Sudoku discutido anteriormente. En este caso, la demostración muestra que una solución de Sudoku en tiempo polinomial también podría usarse para completar cuadrados latinos en tiempo polinomial. [13] Esto a su vez da una solución al problema de dividir gráficas tripartitas 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. Entonces, una solución de tiempo polinomial para Sudoku conduce, mediante una serie de transformaciones mecánicas, a una solución de tiempo polinomial de satisfacibilidad, que a su vez puede usarse para resolver cualquier otro problema NP en tiempo polinomial. Utilizando transformaciones como ésta, una amplia clase de problemas aparentemente no relacionados son todos reducibles entre sí y, en cierto sentido, son "el mismo problema".
Problemas más difíciles
Aunque se desconoce si P = NP , se conocen problemas fuera de P. Así como la clase P se define en términos de tiempo de ejecución polinomial, la clase EXPTIME es el conjunto de todos los problemas de decisión que tienen un tiempo de ejecución exponencial . En otras palabras, cualquier problema en EXPTIME se puede resolver mediante una máquina de Turing determinista en el tiempo O (2 p ( n ) ), donde p ( n ) es una función polinomial de n . Un problema de decisión es EXPTIME -completo si está en EXPTIME , y cada problema en EXPTIME tiene una reducción de varios uno en tiempo polinomial . Se sabe que varios problemas son EXPTIME -complete. Debido a que se puede demostrar que P ≠ EXPTIME , estos problemas están fuera de P y, por lo tanto, requieren más que un tiempo polinómico. De hecho, según el teorema de la jerarquía temporal , no se pueden resolver en un tiempo significativamente menor que exponencial. Los ejemplos incluyen encontrar una estrategia perfecta para posiciones de ajedrez en un tablero N × N [16] y problemas similares para otros juegos de tablero. [17]
El problema de decidir la verdad de un enunciado en la aritmética de Presburger requiere aún más tiempo. Fischer y Rabin demostraron en 1974 [18] que cada algoritmo que decide la verdad de las declaraciones de Presburger de longitud n tiene un tiempo de ejecución de al menospara alguna constante c . Por lo tanto, se sabe que el problema necesita más que un tiempo de ejecución exponencial. Aún más difíciles son los problemas indecidibles , como el problema de la detención . No pueden ser resueltos completamente por ningún algoritmo, en el sentido de que para cualquier algoritmo particular hay al menos una entrada para la cual ese algoritmo no producirá la respuesta correcta; O producirá la respuesta incorrecta, terminará sin dar una respuesta concluyente o, de lo contrario, se ejecutará eternamente sin producir ninguna respuesta.
También es posible considerar cuestiones distintas de los problemas de decisión. Una de esas clases, que consta de problemas de conteo, se llama #P : mientras que un problema NP pregunta "¿Hay alguna solución?", El problema #P correspondiente pregunta "¿Cuántas soluciones hay?" Claramente, un problema #P debe ser al menos tan difícil como el problema NP correspondiente , ya que un conteo de soluciones indica inmediatamente si existe al menos una solución, si el conteo es mayor que cero. Sorprendentemente, algunos problemas #P que se cree que son difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal) . [19] Para estos problemas, es muy fácil saber si existen soluciones, pero se cree que es muy difícil saber cuántas. Muchos de estos problemas son #P -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-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. [1] Estos problemas se denominan problemas intermedios NP . El problema del isomorfismo gráfico , el problema del logaritmo discreto y el problema de la factorización de enteros son ejemplos de problemas que se cree que son NP intermedios. Son algunos de los pocos problemas de NP que no se sabe que están en P o que son NP -completos.
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos . Un problema importante sin resolver en la teoría de la complejidad es si el problema de isomorfismo de grafos está en P , NP -completo o NP -intermedio. La respuesta no se conoce, pero se cree que el problema al menos no es NP -completo. [20] Si el isomorfismo del gráfico es NP -completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. [21] Dado que se cree ampliamente que la jerarquía de polinomios no colapsa a ningún nivel finito, se cree que el isomorfismo de grafos no es NP- completo. El mejor algoritmo para este problema, debido a László Babai y Eugene Luks , tiene un tiempo de ejecución 2 O ( √ n log n ) para gráficos con n vértices.
El problema de factorización de enteros es el problema computacional de determinar la factorización prima de un entero dado. Expresado como un problema de decisión, es el problema de decidir si la entrada tiene un factor menor que k . No se conoce ningún algoritmo de factorización de enteros eficiente, y este hecho constituye la base de varios sistemas criptográficos modernos, como el algoritmo RSA . El problema de factorización de enteros está en NP y en co-NP (e incluso en UP y co-UP [22] ). Si el problema es NP -completo, la jerarquía de tiempo polinomial colapsará a su primer nivel (es decir, NP = co-NP ). El algoritmo más conocido para la factorización de enteros es el tamiz de campo numérico general , que toma el tiempo esperado
para factorizar un número entero de n bits. Sin embargo, el algoritmo cuántico más conocido para este problema, el algoritmo de Shor , se ejecuta en tiempo polinomial, aunque esto no indica dónde radica el problema con respecto a las clases de complejidad no cuántica .
¿P significa "fácil"?
Toda la discusión anterior ha supuesto que P significa "fácil" y "no en P " significa "difícil", una suposición conocida como tesis de Cobham . Es una suposición [ cita requerida ] común y razonablemente precisa en la teoría de la complejidad; sin embargo, tiene algunas salvedades.
Primero, no siempre es cierto en la práctica. Un algoritmo polinomial teórico puede tener factores constantes o exponentes extremadamente grandes, lo que lo vuelve poco práctico. Por ejemplo, el problema de decidir si un grafo G contiene H como un menor de edad , donde H es fijo, puede ser resuelto en un tiempo de ejecución de O ( n 2 ), [24] donde n es el número de vértices en G . Sin embargo, la gran notación O esconde una constante que depende superexponentially en H . La constante es mayor que(usando la notación de flecha hacia arriba de Knuth ), y donde h es el número de vértices en H . [25]
Por otro lado, incluso si se demuestra que un problema es NP- completo, e incluso si P ≠ NP , todavía puede haber enfoques efectivos para abordar el problema en la práctica. Existen algoritmos para muchos problemas NP completos, como el problema de la mochila , el problema del viajante de comercio y el problema de satisfacibilidad booleano , que pueden resolver de manera óptima muchas instancias del mundo real en un tiempo razonable. La complejidad empírica de casos promedio (tiempo versus tamaño del problema) de tales algoritmos puede ser sorprendentemente baja. Un ejemplo es el algoritmo simplex en programación lineal , que funciona sorprendentemente bien en la práctica; a pesar de tener una complejidad de tiempo exponencial en el peor de los casos , se ejecuta a la par con los algoritmos de tiempo polinómico más conocidos. [26]
Por último, existen tipos de cálculos que no se ajustan al modelo de la máquina de Turing en el que se definen P y NP , como el cálculo cuántico y los algoritmos aleatorizados .
Razones para creer que P ≠ NP o P = NP
Según las encuestas, [9] [27] 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 sido capaz de encontrar un algoritmo de tiempo polinomial para ninguno de los más de 3000 problemas NP completos conocidos importantes (ver Lista de problemas NP completos ). Estos algoritmos se buscaron mucho antes de que se definiera el concepto de NP -completo ( los 21 problemas de NP -completos de Karp , entre los primeros encontrados, eran todos problemas existentes bien conocidos en el momento en que se demostró que eran NP -completos). Además, el resultado P = NP implicaría muchos otros resultados sorprendentes que actualmente se cree que son falsos, como NP = co-NP y P = PH .
También se argumenta intuitivamente que la existencia de problemas que son difíciles de resolver pero cuyas soluciones son fáciles de verificar coincide con la experiencia del mundo real. [28]
Si P = NP , entonces el mundo sería un lugar profundamente diferente de lo que solemos asumir. No habría ningún valor especial en los "saltos creativos", 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 existe un exceso de confianza en creer que P ≠ NP y que los investigadores también deberían explorar pruebas de P = NP . Por ejemplo, en 2002 se hicieron estas declaraciones: [9]
El principal argumento a favor de P ≠ NP es la falta total de progreso fundamental en el área de búsqueda exhaustiva. Este es, en mi opinión, un argumento muy débil. El espacio de los algoritmos es muy grande y solo estamos al comienzo de su exploración. [...] La resolución del último teorema de Fermat también muestra que las cuestiones muy simples sólo pueden resolverse mediante teorías muy profundas.
- Moshe Y. Vardi , Universidad Rice
Estar apegado a una especulación no es una buena guía para la planificación de la investigación. Siempre se debe intentar en ambas direcciones de cada problema. El prejuicio ha provocado que matemáticos famosos no hayan podido resolver problemas famosos cuya solución era contraria a sus expectativas, a pesar de que habían desarrollado todos los métodos necesarios.
- Anil Nerode , Universidad de Cornell
Consecuencias de la solución
Una de las razones por las que el problema atrae tanta atención son las consecuencias de las posibles respuestas. Cualquiera de las dos direcciones de resolución haría avanzar la teoría enormemente y quizás también tendría enormes consecuencias prácticas.
P = NP
Una prueba de que P = NP podría tener consecuencias prácticas asombrosas si la prueba conduce a métodos eficientes para resolver algunos de los problemas importantes en NP . Las posibles consecuencias, tanto positivas como negativas, surgen dado que varios problemas NP- completos son fundamentales en muchos campos.
También es muy posible que una demostración no conduzca a algoritmos prácticos para problemas NP completos. La formulación del problema no requiere que el polinomio delimitador sea pequeño o incluso conocido específicamente. Una prueba no constructiva podría mostrar que existe una solución sin especificar un algoritmo para obtenerla o un límite específico. Incluso si la demostración es constructiva, mostrando un polinomio delimitador explícito y detalles algorítmicos, si el polinomio no es de muy bajo orden, el algoritmo podría no ser lo suficientemente eficiente en la práctica. En este caso, la demostración inicial sería de interés principalmente para los teóricos, pero el conocimiento de que las soluciones de tiempo polinomial son posibles sin duda estimularía la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.
Un ejemplo de un campo que podría ser desarraigado por una solución que muestre P = NP es la criptografía , que se basa en la dificultad de ciertos problemas. Una solución constructiva y eficiente [Nota 2] a un problema de NP completo como 3-SAT rompería la mayoría de los criptosistemas existentes, incluidos:
- Implementaciones existentes de criptografía de clave pública , [29] una base para muchas aplicaciones de seguridad modernas, como transacciones financieras seguras a través de Internet.
- Cifrados simétricos como AES o 3DES , [30] utilizados para el cifrado de datos de comunicaciones.
- Hash criptográfico , que subyace a las criptomonedas blockchain como Bitcoin , y se utiliza para autenticar actualizaciones de software. Para estas aplicaciones, el problema de encontrar una imagen previa que tenga un valor determinado debe ser difícil para que sea útil, e idealmente debería requerir un tiempo exponencial. Sin embargo, si P = NP , entonces la búsqueda de una imagen previa M se puede hacer en tiempo polinomial, mediante la reducción a SAT. [31]
Estos tendrían que ser modificados o reemplazados por soluciones teóricamente seguras de información que no se basen inherentemente en la desigualdad P - NP .
Por otro lado, hay enormes consecuencias positivas que se derivarían de hacer manejables muchos problemas matemáticamente insolubles en la actualidad. Por ejemplo, muchos problemas en la investigación de operaciones son NP -completos, como algunos tipos de programación entera y el problema del viajante . Las soluciones eficientes a estos problemas tendrían enormes implicaciones para la logística. Muchos otros problemas importantes, como algunos problemas en la predicción de la estructura de las proteínas , también son NP completos; [32] si estos problemas se pudieran resolver de manera eficiente, podrían impulsar avances considerables en las ciencias de la vida y la biotecnología.
Pero tales cambios pueden palidecer en importancia en comparación con la revolución que un método eficiente para resolver problemas NP- completos causaría en las matemáticas mismas. Gödel, en sus primeros pensamientos sobre la complejidad computacional, señaló que un método mecánico que pudiera resolver cualquier problema revolucionaría las matemáticas: [33] [34]
Si realmente hubiera una máquina con φ (n) ∼ k ⋅ n (o incluso ∼ k ⋅ n 2 ), esto tendría consecuencias de la mayor importancia. Es decir, obviamente significaría que, a pesar de la indecidibilidad del Entscheidungsproblem , el trabajo mental de un matemático sobre preguntas de sí o no podría ser completamente reemplazado por una máquina. Después de todo, uno simplemente tendría que elegir el número natural n tan grande que cuando la máquina no entrega un resultado, no tiene sentido pensar más en el problema.
De manera similar, Stephen Cook (asumiendo no solo una prueba, sino un algoritmo prácticamente eficiente) dice [35]
... transformaría las matemáticas al permitir que una computadora encuentre una prueba formal de cualquier teorema que tenga una prueba de una longitud razonable, ya que las demostraciones formales pueden reconocerse fácilmente en tiempo polinomial. Los problemas de ejemplo pueden incluir todos los problemas de premios de CMI .
Los investigadores matemáticos pasan sus carreras tratando de probar teoremas, y algunas pruebas han tardado décadas o incluso siglos en encontrar después de que se han planteado los problemas; por ejemplo, el último teorema de Fermat tardó más de tres siglos en demostrarse. Un método que esté garantizado para encontrar pruebas de teoremas, si existiera uno de un tamaño "razonable", esencialmente terminaría con esta lucha.
Donald Knuth ha declarado que ha llegado a creer que P = NP , pero se reserva el impacto de una posible prueba: [36]
[...] si imaginas un número M que es finito pero increíblemente grande, como el número 10 ↑↑↑↑ 3 discutido en mi artículo sobre "afrontar la finitud", entonces hay una enorme cantidad de algoritmos posibles que hacen n M bit a bit o operaciones de suma o desplazamiento en n bits dados, y es realmente difícil creer que todos esos algoritmos fallan. Mi punto principal, sin embargo, es que no creo que la igualdad P = NP resulte útil incluso si se prueba, porque esa prueba casi seguramente no será constructiva.
P ≠ NP
Una prueba que mostrara que P ≠ NP carecería de los beneficios computacionales prácticos de una prueba de que P = NP , pero sin embargo representaría un avance muy significativo en la teoría de la complejidad computacional y proporcionaría una guía para futuras investigaciones. Permitiría mostrar de manera formal que muchos problemas comunes no se pueden resolver de manera eficiente, de modo que la atención de los investigadores pueda centrarse en soluciones parciales o soluciones a otros problemas. Debido a la creencia generalizada en P ≠ NP , gran parte de este enfoque de la investigación ya ha tenido lugar. [37]
Además, P ≠ NP todavía deja abierta la complejidad de casos promedio de problemas difíciles en NP . Por ejemplo, es posible que SAT requiera un tiempo exponencial en el peor de los casos, pero que casi todas las instancias seleccionadas al azar se puedan resolver de manera eficiente. Russell Impagliazzo ha descrito cinco "mundos" hipotéticos que podrían resultar de diferentes posibles resoluciones a la pregunta de complejidad del caso promedio. [38] Estos van desde "Algorithmica", donde P = NP y problemas como SAT se pueden resolver de manera eficiente en todos los casos, hasta "Cryptomania", donde P ≠ NP y generar instancias difíciles de problemas fuera de P es fácil, con tres posibilidades intermedias. reflejando diferentes posibles distribuciones de dificultad en casos de NP -problemas difíciles. El "mundo" donde P ≠ NP pero todos los problemas en NP son manejables en el caso promedio se llama "Heurística" en el documento. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos. [39]
Resultados sobre la dificultad de la prueba
Aunque el problema de P = NP permanece abierto a pesar de un premio de un millón de dólares y una gran cantidad de investigación dedicada, los esfuerzos para resolver el problema han llevado a varias técnicas nuevas. En particular, algunas de las investigaciones más fructíferas relacionadas con el problema P = NP han demostrado que las técnicas de prueba existentes no son lo suficientemente poderosas para responder a la pregunta, lo que sugiere que se requieren enfoques técnicos novedosos.
Como evidencia adicional de la dificultad del problema, esencialmente todas las técnicas de prueba conocidas en la teoría de la complejidad computacional caen en una de las siguientes clasificaciones, cada una de las cuales se sabe que es insuficiente para demostrar que P ≠ NP :
Clasificación | Definición |
---|---|
Pruebas relativizantes | Imagine un mundo en el que cada algoritmo puede realizar consultas a una subrutina fija llamada oráculo (una caja negra que puede responder a un conjunto fijo de preguntas en tiempo constante, como una caja negra que resuelve cualquier problema de viajante en un solo paso). , y el tiempo de ejecución del oráculo no se cuenta contra el tiempo de ejecución del algoritmo. La mayoría de las pruebas (especialmente las clásicas) se aplican uniformemente en un mundo con oráculos independientemente de lo que haga el oráculo. Estas pruebas se llaman relativizantes . En 1975, Baker, Gill y Solovay demostraron que P = NP con respecto a algunos oráculos, mientras que P ≠ NP para otros oráculos. [40] Dado que las demostraciones de relativización solo pueden probar afirmaciones que son uniformemente verdaderas con respecto a todos los oráculos posibles, esto demostró que las técnicas de relativización no pueden resolver P = NP . |
Pruebas naturales | En 1993, Alexander Razborov y Steven Rudich definieron una clase general de técnicas de prueba para límites inferiores de complejidad de circuito, llamadas pruebas naturales . [41] En ese momento, todos los límites inferiores de los circuitos conocidos anteriormente eran naturales, y la complejidad del circuito se consideraba un enfoque muy prometedor para resolver P = NP . Sin embargo, Razborov y Rudich demostraron que, si existen funciones unidireccionales , ningún método de prueba natural puede distinguir entre P y NP . Aunque nunca se ha demostrado formalmente que existan funciones unidireccionales, la mayoría de los matemáticos creen que sí, y una prueba de su existencia sería una afirmación mucho más fuerte que P ≠ NP . Por lo tanto, es poco probable que las pruebas naturales por sí solas puedan resolver P = NP . |
Pruebas de algebrización | Después del resultado de Baker-Gill-Solovay, se utilizaron con éxito nuevas técnicas de prueba no relativizantes para demostrar que IP = PSPACE . Sin embargo, en 2008, Scott Aaronson y Avi Wigderson demostraron que la principal herramienta técnica utilizada en la prueba IP = PSPACE , conocida como aritmetización , también era insuficiente para resolver P = NP . [42] |
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 que los resultados anteriores no excluyen.
Estas barreras también han llevado a algunos científicos informáticos a sugerir que el problema de P versus NP puede ser independiente de los sistemas de axiomas estándar como ZFC (no se puede probar ni refutar dentro de ellos). La interpretación de un resultado de independencia podría ser que no existe un algoritmo de tiempo polinomial para ningún problema NP- completo, y tal demostración no se puede construir en (por ejemplo) ZFC, o que pueden existir algoritmos de tiempo polinomial para problemas NP- completos, pero es imposible probar en ZFC que tales algoritmos sean correctos. [43] 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 extienden los axiomas de Peano (PA) para aritmética de enteros, entonces necesariamente habría existen algoritmos de tiempo casi polinomial para cada problema en NP . [44] Por lo tanto, si uno cree (como hacen la mayoría de los teóricos de la complejidad) que no todos los problemas en NP tienen algoritmos eficientes, se deduciría que las pruebas de independencia utilizando esas técnicas no pueden ser posibles. Además, este resultado implica que demostrar la independencia de PA o ZFC utilizando técnicas conocidas actualmente no es más fácil que demostrar la existencia de algoritmos eficientes para todos los problemas en NP .
Soluciones reclamadas
Si bien el problema de P versus NP generalmente se considera sin resolver, [45] muchos investigadores aficionados y algunos profesionales han afirmado que existen soluciones. Gerhard J. Woeginger mantiene una lista que, a partir de 2018, contiene 62 supuestas pruebas de P = NP , 50 pruebas de P ≠ NP , 2 pruebas de que el problema es indemostrable y una prueba de que es indecidible. [46] Algunos intentos de resolver P versus NP han recibido una breve atención de los medios, [47] aunque estos intentos han sido refutados desde entonces.
Caracterizaciones lógicas
El problema P = NP puede reformularse en términos de ciertas clases de enunciados lógicos expresables, como resultado del trabajo en complejidad descriptiva .
Considere todos los lenguajes de estructuras finitas con una firma fija que incluye una relación de orden lineal . Entonces, todos estos lenguajes en P se pueden expresar en lógica de primer orden con la adición de un combinador de punto fijo mínimo adecuado . Efectivamente, esto, en combinación con el orden, permite la definición de funciones recursivas. Mientras la firma contiene al menos un predicado o función además de la relación de orden distinguido, de modo que la cantidad de espacio necesario para almacenar tales estructuras finitas es en realidad polinomio en el número de elementos en la estructura, esto caracteriza precisamente P .
De manera similar, NP es el conjunto de lenguajes que se pueden expresar en la lógica existencial de segundo orden , es decir, la lógica de segundo orden restringida para excluir la cuantificación universal sobre relaciones, funciones y subconjuntos. Los lenguajes de la jerarquía polinómica , PH , corresponden a toda la lógica de segundo orden. Por lo tanto, la pregunta "¿es P un subconjunto adecuado de NP " puede reformularse como "es la lógica existencial de segundo orden capaz de describir lenguajes (de estructuras finitas ordenadas linealmente con firma no trivial) que la lógica de primer orden con el mínimo punto fijo no puede?" . [48] La palabra "existencial" incluso se puede quitar de la caracterización anterior, ya que P = NP si y solo si P = PH (ya que la primera establecería que NP = co-NP , lo que a su vez implica que NP = PH ) .
Algoritmos de tiempo polinomial
No se conoce ningún algoritmo para ningún problema de NP completo que se ejecute en tiempo polinomial. Sin embargo, existen algoritmos conocidos para problemas NP -completos con la propiedad de que si P = NP , entonces el algoritmo se ejecuta en tiempo polinomial al aceptar instancias (aunque con constantes enormes, lo que hace que el algoritmo no sea práctico). Sin embargo, estos algoritmos no califican como tiempo polinomial porque su tiempo de ejecución al rechazar instancias no es polinomial. El siguiente algoritmo, debido a Levin (sin ninguna cita), es un ejemplo a continuación. Acepta correctamente el lenguaje NP -completo SUBSET-SUM . Se ejecuta en tiempo polinomial en entradas que están en SUBSET-SUM si y solo si P = NP :
// Algoritmo que acepta el lenguaje NP -completo SUBSET-SUM. // // este es un algoritmo de tiempo polinomial si y solo si P = NP . // // "Polinomio-tiempo" 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 // escribiendo el entero M en binario, luego // considerando que esa cadena de bits es un // programa. Todos los programas posibles se pueden // generar de esta manera, aunque la mayoría no hace nada // debido a errores de sintaxis.PARA K = 1 ... ∞ PARA M = 1 ... K Ejecute el programa número M para K pasos con la entrada S SI el programa genera una lista de enteros distintos Y los enteros están todos en S Y los enteros suman 0 LUEGO SALIDA "sí" y DETENER
Si, y solo si, P = NP , entonces este es un algoritmo de tiempo polinomial que acepta un lenguaje NP -completo. "Aceptar" significa que da respuestas "sí" en tiempo polinomial, pero se permite que se ejecute indefinidamente cuando la respuesta es "no" (también conocido como semialgoritmo ).
Este algoritmo es enormemente impráctico, incluso si P = NP . Si el programa más corto que puede resolver SUBSET-SUM en tiempo polinomial tiene una longitud de b bits, el algoritmo anterior probará al menos 2 b - 1 otros programas primero.
Definiciones formales
P y NP
Hablando conceptualmente, un problema de decisión es un problema que toma como entrada alguna cadena w sobre un alfabeto Σ, y da como resultado "sí" o "no". Si hay un algoritmo (digamos una máquina de Turing o un programa de computadora con memoria ilimitada) que puede producir la respuesta correcta para cualquier cadena de entrada de longitud n en como máximo cn k pasos, donde k y c son constantes independientes de la cadena de entrada , entonces se dice que el problema puede ser resuelto en tiempo polinómico y lo colocamos en la clase P . Formalmente, P se define como el conjunto de todos los lenguajes que pueden ser decididos por una máquina de Turing determinista de tiempo polinomial. Es decir,
dónde
y una máquina de Turing determinista de tiempo polinomial es una máquina de Turing determinista M que satisface las dos condiciones siguientes:
- M se detiene en todas las entradas W y
- existe tal que , donde O se refiere a la notación O grande y
NP se puede definir de manera similar utilizando máquinas de Turing no deterministas (la forma tradicional). Sin embargo, un enfoque moderno para definir NP es utilizar el concepto de certificado y verificador . Formalmente, NP se define como el conjunto de idiomas sobre un alfabeto finito que tienen un verificador que se ejecuta en tiempo polinomial, donde la noción de "verificador" se define de la siguiente manera.
Sea L una lengua sobre un alfabeto finito, Σ.
L ∈ NP si, y solo si, existe una relación binariay un entero positivo k tal que se satisfagan las dos condiciones siguientes:
- Para todos , tal que ( x , y ) ∈ R y; y
- el idioma encima es decidible por una máquina de Turing determinista en tiempo polinomial.
La máquina A Turing que decide L R se llama un verificador de L y un y tal que ( x , y ) ∈ R se denomina un certificado de pertenencia de x en L .
En general, un verificador no tiene por qué ser de tiempo polinómico. Sin embargo, para que L esté en NP , debe haber un verificador que se ejecute en tiempo polinomial.
Ejemplo
Dejar
Claramente, la cuestión de si una x dada es un compuesto es equivalente a la cuestión de si x es un miembro de COMPOSITE. Se puede demostrar que COMPOSITE ∈ NP verificando que satisface la definición anterior (si identificamos números naturales con sus representaciones binarias).
COMPOSITE también está en P , un hecho demostrado por la invención de la prueba de primalidad AKS . [49]
NP-completitud
Hay muchas formas equivalentes de describir la completitud de NP .
Sea L una lengua sobre un alfabeto finito Σ.
L es NP -completo si, y solo si, se cumplen las dos condiciones siguientes:
- L ∈ NP ; y
- cualquier L ' en NP es polinomial-tiempo-reducible a L (escrito como), dónde si, y solo si, se cumplen las dos condiciones siguientes:
- Existe f : Σ * → Σ * tal que para todo w en Σ * tenemos:; y
- existe una máquina de Turing de tiempo polinomial que se detiene con f ( w ) en su cinta en cualquier entrada w .
Alternativamente, si L ∈ NP , y hay otro problema NP -completo que puede reducirse en tiempo polinómico a L , entonces L es NP -completo. Esta es una forma común de probar que algún problema nuevo es NP -completo.
Cultura popular
La película Travelling Salesman , del director Timothy Lanzone, es la historia de cuatro matemáticos contratados por el gobierno de Estados Unidos para resolver el problema P versus NP . [50]
En el sexto episodio de la séptima temporada de Los Simpson , " Treehouse of Horror VI ", la ecuación P = NP se ve poco después de que Homer accidentalmente se topa con la "tercera dimensión". [51] [52]
En el segundo episodio de la temporada 2 de Elementary , "Resuelve para X" gira en torno a Sherlock y Watson que investigan los asesinatos de matemáticos que intentaban resolver P contra NP . [53] [54]
Ver también
- Complejidad del juego
- Lista de problemas matemáticos sin resolver
- Conjetura de juegos únicos
- Problemas no resueltos en informática
Notas
- ^ Una máquina de Turing no determinista puede pasar a un estado que no está determinado por el estado anterior. Tal máquina podría resolver unproblema NP en tiempo polinomial al caer en el estado de respuesta correcto (por suerte) y luego verificarlo de manera convencional. Estas máquinas no son prácticas para resolver problemas realistas, pero pueden usarse como modelos teóricos.
- ^ Exactamente qué tan eficiente debe ser una solución para representar una amenaza para la criptografía depende de los detalles. Una solucion decon un término constante razonable sería desastroso. Por otro lado, una solución que es en casi todos los casos no supondría un peligro práctico inmediato.
Referencias
- ^ a b R. E. Ladner "Sobre la estructura de la reducibilidad del tiempo polinomial", Journal of the ACM 22, págs. 151-171, 1975. Corolario 1.1. Sitio de ACM .
- ↑ Fortnow, Lance (2013). El boleto de oro: P, NP y la búsqueda de lo imposible . Princeton, Nueva Jersey: Princeton University Press. ISBN 9780691156491.
- ^ Cook, Stephen (1971). "La complejidad de los procedimientos de demostración de teoremas" . Actas del Tercer Simposio Anual ACM sobre Teoría de la Computación . págs. 151-158.
- ^ LA Levin (1973). "Универсальные задачи перебора" (en ruso). 9 (3) (Problemas de transmisión de información ed.): 115-116. Cite journal requiere
|journal=
( ayuda ) - ^ Fortnow, Lance (2009). "El estado del problema P versus NP " (PDF) . Comunicaciones de la ACM . 52 (9): 78–86. CiteSeerX 10.1.1.156.767 . doi : 10.1145 / 1562164.1562186 . Archivado desde el original (PDF) el 24 de febrero de 2011 . Consultado el 26 de enero de 2010 .
- ^ NSA (2012). "Cartas de John Nash" (PDF) .
- ^ Hartmanis, Juris. "Gödel, von Neumann y el problema P = NP " (PDF) . Boletín de la Asociación Europea de Informática Teórica . 38 : 101-107.
- ^ 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.
- ^ a b c William I. Gasarch (junio de 2002). "La encuesta P =? NP " (PDF) . Noticias SIGACT . 33 (2): 34–47. CiteSeerX 10.1.1.172.1005 . doi : 10.1145 / 564585.564599 .
- ^ William I. Gasarch . "La segunda encuesta P =? NP " (PDF) . Noticias SIGACT . 74 .
- ^ a b "Columna de invitado: el tercer P =? NP Poll1" (PDF) . Consultado el 25 de mayo de 2020 .
- ^ Scott Aaronson. "PHYS771 Lectura 6: P , NP y amigos" . Consultado el 27 de agosto de 2007 .
- ^ "Curso de maestría: Fundamentos de la informática" . www.cs.ox.ac.uk . Consultado el 25 de mayo de 2020 .
- ^ 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 .
- ^ I. Holyer (1981). "El NP -completitud de algunos problemas de partición de borde". SIAM J. Comput . 10 (4): 713–717. doi : 10.1137 / 0210054 .
- ^ Aviezri Fraenkel y D. Lichtenstein (1981). "Calcular una estrategia perfecta para n × n ajedrez requiere tiempo exponencial en n " . Revista de Teoría Combinatoria, serie A . 31 (2): 199–214. doi : 10.1016 / 0097-3165 (81) 90016-9 .
- ^ David Eppstein . "Complejidad computacional de juegos y rompecabezas" .
- ^ Fischer, Michael J .; Rabin, Michael O. (1974). "Complejidad superexponencial de la aritmética de Presburger" . Actas del Simposio SIAM-AMS en Matemática Aplicada . 7 : 27–41. Archivado desde el original el 15 de septiembre de 2006 . Consultado el 15 de octubre de 2017 .
- ^ Valiente, Leslie G. (1979). "La complejidad de problemas de enumeración y fiabilidad". Revista SIAM de Computación . 8 (3): 410–421. doi : 10.1137 / 0208032 .
- ^ Arvind, Vikraman; Kurur, Piyush P. (2006). "El isomorfismo gráfico está en SPP " . Información y Computación . 204 (5): 835–852. doi : 10.1016 / j.ic.2006.02.002 .
- ^ Schöning, Uwe (1988). "El isomorfismo gráfico está en la jerarquía baja". Revista de Ciencias de la Computación y Sistemas . 37 (3): 312–323. doi : 10.1016 / 0022-0000 (88) 90010-4 .
- ^ Lance Fortnow . Blog de complejidad computacional: Clase de complejidad de la semana: Factorización . 13 de septiembre de 2002.
- ^ Pisinger, D. 2003. "¿Dónde están los problemas de la mochila dura?" Informe técnico 2003/08, Departamento de Ciencias de la Computación, Universidad de Copenhague, Copenhague, Dinamarca
- ^ Kawarabayashi, KI; Kobayashi, Y .; Reed, B. (2012). "El problema de los caminos disjuntos en el tiempo cuadrático" . Revista de Teoría Combinatoria, Serie B . 102 (2): 424–435. doi : 10.1016 / j.jctb.2011.07.004 .
- ^ Johnson, David S. (1987). "La columna NP-completitud: una guía continua (edición 19)". Revista de algoritmos . 8 (2): 285-303. CiteSeerX 10.1.1.114.3864 . doi : 10.1016 / 0196-6774 (87) 90043-5 .
- ^ Gondzio, Jacek; Terlaky, Tamás (1996). "3 Una vista computacional de los métodos de puntos interiores" . En JE Beasley (ed.). Avances en programación lineal y entera . Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones. 4 . Nueva York: Oxford University Press. págs. 103-144. Señor 1438311 . Archivo PostScript en el sitio web de Gondzio y en el sitio web de Terlaky de la Universidad McMaster .
- ^ Rosenberger, Jack (mayo de 2012). " Resultados de la encuesta P vs NP " . Comunicaciones de la ACM . 55 (5): 10.
- ^ Scott Aaronson. "Razones para creer" ., punto 9.
- ^ Ver Horie, S .; Watanabe, O. (1997). "Generación de instancias duras para SAT". Algoritmos y Computación . Apuntes de conferencias en informática. 1350 . Saltador. págs. 22–31. arXiv : cs / 9809117 . Código Bibliográfico : 1998cs ........ 9117H . doi : 10.1007 / 3-540-63890-3_4 . ISBN 978-3-540-63890-2.para una reducción del factoring al SAT. Un problema de factorización de 512 bits (8400 MIPS-años cuando se factoriza) se traduce en un problema SAT de 63.652 variables y 406.860 cláusulas.
- ^ Ver, por ejemplo, Massacci, F. y Marraro, L. (2000). "Criptoanálisis lógico como problema SAT". Revista de razonamiento automatizado . 24 (1): 165-203. CiteSeerX 10.1.1.104.962 . doi : 10.1023 / A: 1006326723002 .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 sería aproximadamente 3 veces este tamaño.
- ^ De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Ataques de inversión a funciones hash seguras utilizando solucionadores SAT". Saltador. págs. 377–382. doi : 10.1007 / 978-3-540-72788-0_36 . Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Berger B , Leighton T (1998). "El plegamiento de proteínas en el modelo hidrofóbico-hidrofílico (HP) es NP- completo". J. Comput. Biol . 5 (1): 27–40. CiteSeerX 10.1.1.139.5547 . doi : 10.1089 / cmb.1998.5.27 . PMID 9541869 .
- ^ Historia de esta carta y su traducción de Michael Sipser. "La historia y el estado de la pregunta P versus NP " (PDF) .
- ^ David S. Johnson. "Una breve historia de NP-Completeness, 1954-2012" .De las páginas 359–376 de Optimization Stories, M. Grötschel (editor), un número especial de ¨ Documenta Mathematica, publicado en agosto de 2012 y distribuido a los asistentes al 21º Simposio Internacional de Programación Matemática en Berlín.
- ^ Cook, Stephen (abril de 2000). "El problema de P versus NP " (PDF) . Instituto Clay de Matemáticas . Consultado el 18 de octubre de 2006 . Cite journal requiere
|journal=
( ayuda ) - ^ Knuth, Donald E. (20 de mayo de 2014). Veinte preguntas para Donald Knuth . informit.com . InformIT . Consultado el 20 de julio de 2014 .
- ^ LR Foulds (octubre de 1983). "El enfoque heurístico de resolución de problemas". Revista de la Sociedad de Investigación Operativa . 34 (10): 927–934. doi : 10.2307 / 2580891 . JSTOR 2580891 .
- ^ R. Impagliazzo, "Una visión personal de la complejidad del caso promedio" , sct, págs. 134, décima conferencia anual sobre la estructura en la teoría de la complejidad (SCT'95), 1995
- ^ "Programa tentativo para el taller sobre" Complejidad y criptografía: estado de los mundos de Impagliazzo " " . Archivado desde el original el 15 de noviembre de 2013.
- ^ TP Baker; J. Gill; R. Solovay. (1975). "Relativizaciones de la pregunta P =? NP ". Revista SIAM de Computación . 4 (4): 431–442. doi : 10.1137 / 0204037 .
- ^ Razborov, Alexander A .; Steven Rudich (1997). "Pruebas naturales". Revista de Ciencias de la Computación y Sistemas . 55 (1): 24–35. doi : 10.1006 / jcss.1997.1494 .
- ^ S. Aaronson y A. Wigderson (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 .
- ^ Aaronson, Scott . "¿Es P versus NP formalmente independiente?" (PDF) ..
- ^ Ben-David, Shai; Halevi, Shai (1992). "Sobre la independencia de P frente a NP " . Reporte técnico. 714 . Technion. Cite journal requiere
|journal=
( ayuda ). - ^ John Markoff (8 de octubre de 2009). "Premios aparte, el rompecabezas P-NP tiene consecuencias" . The New York Times .
- ^ Gerhard J. Woeginger . "La página P -versus- NP " . Consultado el 24 de junio de 2018 .
- ^ Markoff, John (16 de agosto de 2010). "Paso 1: Publicar prueba escurridiza. Paso 2: Ver los fuegos artificiales" . The New York Times . Consultado el 20 de septiembre de 2010 .
- ^ Elvira Mayordomo. "P versus NP" Archivado el 16 de febrero de 2012 en la Wayback Machine. Monografías de la Real Academia de Ciencias de Zaragoza 26 : 57–68 (2004).
- ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P " (PDF) . Annals of Mathematics . 160 (2): 781–793. doi : 10.4007 / annals.2004.160.781 . JSTOR 3597229 .
- ^ Geere, Duncan (26 de abril de 2012). " La película ' Travelling Salesman' considera las repercusiones si P es igual a NP" . Reino Unido cableado . Consultado el 26 de abril de 2012 .
- ^ Difícilmente, Larry. "Explicado: P vs. NP " .
- ^ Shadia, Ajam. "¿Cuál es el problema P vs. NP ? ¿Por qué es importante?" .
- ^ Gasarch, William (7 de octubre de 2013). "¿P vs NP es elemental? No, P vs NP es elemental" . blog.computationalcomplexity.org . Consultado el 6 de julio de 2018 .
- ^ Kirkpatrick, Noel (4 de octubre de 2013). "Resolver elemental para X revisión: Sines of Murder" . TV.com . Consultado el 6 de julio de 2018 .
Otras lecturas
- Cormen, Thomas (2001). Introducción a los algoritmos . Cambridge: MIT Press . ISBN 978-0-262-03293-3.
- Garey, Michael; Johnson, David (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . San Francisco: WH Freeman and Company . ISBN 978-0-7167-1045-5.
- Goldreich, Oded (2010). P, NP y NP-Completitud . Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Borradores en línea
- Immerman, N. (1987). "Idiomas que capturan clases de complejidad". Revista SIAM de Computación . 16 (4): 760–778. CiteSeerX 10.1.1.75.3035 . doi : 10.1137 / 0216051 .
- Papadimitriou, Christos (1994). Complejidad computacional . Boston: Addison-Wesley. ISBN 978-0-201-53082-7.
enlaces externos
- Fortnow, L .; Gasarch, W. "Complejidad computacional" .
- Aviad de Rubinstein dureza de aproximación entre P y NP , ganador de la ACM 's 2017 Premio Tesis Doctoral .
- "P vs NP y el zoológico de complejidad computacional" . 26 de agosto de 2014 - vía YouTube .