Si es fácil comprobar que la solución a un problema es correcta, ¿debe ser fácil de resolver el problema?
El problema P versus NP es un importante problema sin resolver en la informática teórica . De manera informal, se pregunta si todos los problemas cuya solución puede verificarse rápidamente también pueden resolverse rápidamente.
Aquí, rápidamente significa que existe un algoritmo que resuelve la tarea y se ejecuta en tiempo polinómico , lo que significa que el tiempo de finalización de la tarea varía como una función polinómica en el tamaño de la entrada al algoritmo (a diferencia de, digamos, el tiempo exponencial ). La clase general de preguntas que algún algoritmo puede responder en tiempo polinómico es " P " o " clase P ". Para algunas preguntas, no existe una forma conocida de encontrar una respuesta rápidamente, pero si se proporciona una respuesta, se puede verificar rápidamente. La clase de preguntas donde se puede verificar una respuesta en tiempo polinómico es NP , que significa "tiempo polinómico no determinista". [Nota 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 ampliamente, significaría que hay problemas en NP que son más difíciles de calcular que de verificar: no podrían resolverse en tiempo polinomial, pero la respuesta podría verificarse en tiempo polinomial.
El problema ha sido llamado el problema abierto más importante en informática . [1] 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]
Es uno de los siete Problemas del Premio del Milenio seleccionados por el Clay Mathematics Institute , cada uno de los cuales otorga un premio de 1.000.000 de dólares a la primera solución correcta.
En el juego Sudoku , el jugador comienza con una cuadrícula de números parcialmente completada e intenta completar la cuadrícula siguiendo las reglas del juego. Ante una cuadrícula de Sudoku incompleta, de cualquier tamaño, ¿existe al menos una solución legal? Las soluciones propuestas se verifican fácilmente y el tiempo para verificar una solución aumenta lentamente (polinomialmente) a medida que la cuadrícula se hace más grande. Sin embargo, todos los algoritmos conocidos para encontrar soluciones toman, en ejemplos difíciles, un tiempo que crece exponencialmente a medida que la cuadrícula se hace más grande. Entonces, el Sudoku está en NP (rápidamente comprobable) pero no parece estar en P (rápidamente solucionable). Miles de otros problemas parecen igualmente 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 estos problemas no se pueden resolver rápidamente, aunque esto no está demostrado.
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" [3] (e independientemente por Leonid Levin en 1973 [4] ).
Aunque el problema P versus NP se definió formalmente en 1971, ya había indicios de los problemas involucrados, la dificultad de la prueba y las posibles consecuencias. En 1955, el matemático John Nash escribió una carta a la NSA , especulando que descifrar un código suficientemente complejo requeriría un tiempo exponencial en la longitud de la clave. [5] Si se demuestra (y Nash se mostró adecuadamente escéptico), esto implicaría lo que ahora se llama P ≠ NP, ya que una clave propuesta se puede verificar en tiempo polinomial. Otra mención del problema subyacente se produjo en una carta de 1956 escrita por Kurt Gödel a John von Neumann . Gödel preguntó si la demostración de teoremas (que ahora se sabe que es co-NP-completa ) podría resolverse en tiempo cuadrático o lineal , [6] y señaló una de las consecuencias más importantes: que, de ser así, entonces el descubrimiento de demostraciones matemáticas podría resolverse. ser automatizado.
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 trata de los recursos necesarios durante la computación para resolver un problema determinado. Los recursos más comunes son el tiempo (cuántos pasos se necesitan para resolver un problema) y el espacio (cuánta memoria se necesita para resolver un problema).
En tal análisis, se requiere un modelo de computadora para el cual se debe analizar el tiempo. Normalmente, estos modelos suponen que la computadora es determinista (dado su estado actual y cualquier entrada, sólo hay una acción posible que la computadora podría realizar) y secuencial (realiza acciones una tras otra).
En esta teoría, la clase P consta de todos los problemas de decisión (definidos a continuación) que se pueden resolver en una máquina secuencial determinista en un polinomio de duración en el tamaño de la entrada; la clase NP 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 . [7] Claramente, P ⊆ NP. Podría decirse que la mayor pregunta abierta en informática teórica se refiere a la relación entre esas dos clases:
Desde 2002, William Gasarch ha realizado tres encuestas a investigadores sobre esta y otras cuestiones relacionadas. [8] [9] [10] La confianza en que P ≠ NP ha ido aumentando: en 2019, el 88 % creía que P ≠ NP, en comparación con el 83 % en 2012 y el 61 % en 2002. Cuando se restringieron a expertos, las respuestas de 2019 se convirtieron en El 99% creía que P ≠ NP. [10] Estas encuestas no implican si P = NP, el propio Gasarch afirmó: "Esto no nos acerca más a resolver P=?NP o a saber cuándo se resolverá, pero intenta ser un informe objetivo sobre la Opinión subjetiva de esta época."
Para abordar la cuestión P = NP, el concepto de completitud NP es muy útil. Los problemas NP-completos son problemas a los que cualquier otro problema NP es reducible en tiempo polinomial y cuya solución aún es verificable en tiempo polinomial. Es decir, cualquier problema NP se puede transformar en cualquier problema NP completo. Informalmente, 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 al menos tan difíciles como los problemas NP; es decir, todos los problemas NP se pueden reducir (en tiempo polinomial) a ellos. Los problemas NP-difíciles no tienen por qué estar en NP; es decir, no necesitan tener soluciones verificables en tiempo polinomial.
Por ejemplo, el problema de satisfacibilidad booleano es NP-completo según el teorema de Cook-Levin , por lo que cualquier instancia de cualquier problema en NP se puede transformar mecánicamente en un problema de satisfacibilidad booleano en tiempo polinomial. El problema booleano de satisfacibilidad es uno de muchos problemas NP-completos. Si cualquier problema NP-completo está en P, entonces se deduciría que P = NP. Sin embargo, muchos problemas importantes son NP-completos y no se conoce ningún algoritmo rápido para ninguno de ellos.
Sólo a partir de la definición no es intuitivo que existan problemas NP-completos; sin embargo, un problema NP-completo trivial se puede formular de la siguiente manera: dada una máquina de Turing M garantizada para detenerse en tiempo polinómico, ¿existe una entrada de tamaño polinomial que M acepte? [11] Está en NP porque (dada una entrada) es sencillo verificar si M acepta la entrada simulando M ; es NP-completo porque el verificador de 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 de sí o no se determina en función de si existe una entrada válida.
El primer problema natural que demostró ser NP completo fue el problema de satisfacibilidad booleano, también conocido como SAT. Como se señaló anteriormente, este es el teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP-completa contiene detalles técnicos sobre las máquinas de Turing en relación con la definición de NP. Sin embargo, después de que se demostró que este problema era NP completo, la prueba por reducción proporcionó una manera más sencilla de demostrar que muchos otros problemas también son NP completos, incluido el juego Sudoku discutido anteriormente. En este caso, la prueba muestra que una solución de Sudoku en tiempo polinómico también podría usarse para completar cuadrados latinos en tiempo polinómico. [12] Esto a su vez da una solución al problema de dividir gráficos tripartitos en triángulos, [13] que luego podría usarse para encontrar soluciones para el caso especial de SAT conocido como 3-SAT, [14] que luego proporciona una solución para la satisfacibilidad booleana general. Entonces, una solución de Sudoku en tiempo polinomial conduce, mediante una serie de transformaciones mecánicas, a una solución de satisfacibilidad en tiempo polinomial, que a su vez puede usarse para resolver cualquier otro problema NP en tiempo polinomial. Utilizando transformaciones como esta, una amplia clase de problemas aparentemente no relacionados son todos reducibles entre sí y, en cierto sentido, son "el mismo problema".
Aunque se desconoce si P = NP, se conocen problemas fuera de P. Así como la clase P se define en términos de tiempo de ejecución polinomial, la clase EXPTIME es el conjunto de todos los problemas de decisión que tienen tiempo de ejecución exponencial . En otras palabras, cualquier problema en EXPTIME se puede resolver mediante una máquina de Turing determinista en tiempo O (2 p ( n ) ), donde p ( n ) es una función polinómica de n . Un problema de decisión es EXPTIME-completo si está en EXPTIME, y cada problema en EXPTIME tiene una reducción de muchos uno en tiempo polinomial . Se sabe que varios problemas son EXPTIME-completos. Como se puede demostrar que P ≠ EXPTIME, estos problemas están fuera de P y, por tanto, requieren más que tiempo polinomial. De hecho, según el teorema de la jerarquía temporal , no se pueden resolver en un tiempo significativamente menor que el exponencial. Los ejemplos incluyen encontrar una estrategia perfecta para posiciones de ajedrez en un tablero N × N [15] y problemas similares para otros juegos de mesa. [dieciséis]
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 [17] que cada algoritmo que decide la verdad de las declaraciones de Presburger de longitud n tiene un tiempo de ejecución de al menos para alguna constante c . Por lo tanto, se sabe que el problema necesita más que un tiempo de ejecución exponencial. Aún más difíciles son los problemas indecidibles , como el problema de la detención . No pueden resolverse completamente mediante ningún algoritmo, en el sentido de que para cualquier algoritmo en particular hay al menos una entrada para la cual ese algoritmo no producirá la respuesta correcta; producirá una respuesta incorrecta, terminará sin dar una respuesta concluyente o se ejecutará para siempre sin producir ninguna respuesta.
También es posible considerar otras cuestiones además 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 recuento de soluciones indica inmediatamente si existe al menos una solución, si el recuento es mayor que cero. Sorprendentemente, algunos problemas #P que se creen difíciles corresponden a problemas P fáciles (por ejemplo, de tiempo lineal). [18] Para estos problemas, es muy fácil saber si existen soluciones, pero se cree que es muy difícil decir cuántas. Muchos de estos problemas son #P-completos y, por lo tanto, se encuentran entre los problemas más difíciles de #P, ya que una solución en tiempo polinomial para cualquiera de ellos permitiría una solución en tiempo polinomial para todos los demás problemas de #P.
En 1975, Richard E. Ladner demostró que si P ≠ NP, entonces existen problemas en NP que no son ni en P ni en NP completos. [19] Estos problemas se denominan problemas NP-intermedios. El problema del isomorfismo gráfico , el problema del logaritmo discreto y el problema de factorización de números enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas NP que no se sabe que estén en P o que sean NP completos.
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomórficos . 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. Se desconoce la respuesta, 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 polinomial no colapsa a ningún nivel finito, se cree que el isomorfismo del gráfico no es NP-completo. El mejor algoritmo para este problema, obra de László Babai , se ejecuta en tiempo cuasipolinomial . [22]
El problema de factorización de números enteros es el problema computacional de determinar la factorización prima de un número 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 números enteros está en NP y en co-NP (e incluso en UP y co-UP [23] ). Si el problema es NP-completo, la jerarquía temporal polinómica colapsará a su primer nivel (es decir, NP = co-NP). El algoritmo conocido más eficiente para la factorización de números enteros es el tamiz de campo numérico general , que requiere el tiempo esperado.
para factorizar un número entero de n bits. El algoritmo cuántico más conocido para este problema, el algoritmo de Shor , se ejecuta en tiempo polinómico, aunque esto no indica dónde radica el problema con respecto a las clases de complejidad no cuánticas .
Toda la discusión anterior ha asumido que P significa "fácil" y "no en P" significa "difícil", una suposición conocida como tesis de Cobham . Es una suposición común y razonablemente precisa [ cita necesaria ] en la teoría de la complejidad; pero hay salvedades.
En primer lugar, puede ser falso en la práctica. Un algoritmo polinomial teórico puede tener factores constantes o exponentes extremadamente grandes, lo que lo hace poco práctico. Por ejemplo, el problema de decidir si un gráfico G contiene H como menor , donde H es fijo , se puede resolver en un tiempo de ejecución de O ( n 2 ), [25] donde n es el número de vértices en G. Sin embargo, la notación O grande esconde una constante que depende superexponencialmente de H. La constante es mayor que ( usando la notación de flecha hacia arriba de Knuth ), y donde h es el número de vértices en H. [26]
Por 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 booleano de satisfacibilidad , que pueden resolver de forma óptima muchos casos del mundo real en un tiempo razonable. La complejidad empírica promedio de los casos (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 de los algoritmos de tiempo polinomial más conocidos. [27]
Finalmente, existen tipos de cálculos que no se ajustan al modelo de máquina de Turing en el que se definen P y NP, como la computación cuántica y los algoritmos aleatorios .
Cook proporciona una reformulación del problema en El problema P versus NP como "¿P = NP?" [28] Según las encuestas, [8] [29] la mayoría de los informáticos creen que P ≠ NP. Una razón clave para esta creencia es que después de décadas de estudiar estos problemas, nadie ha podido encontrar un algoritmo de tiempo polinomial para ninguno de los más de 3000 importantes problemas NP-completos conocidos (ver Lista de problemas NP-completos ). Estos algoritmos se buscaron mucho antes de que se definiera siquiera el concepto de NP-completo (los 21 problemas NP-completos de Karp , entre los primeros encontrados, eran todos problemas existentes bien conocidos en el momento en que se demostró que eran NP-completos). Además, el resultado P = NP implicaría muchos otros resultados sorprendentes que actualmente se creen falsos, como NP = co-NP y P = PH .
También se argumenta intuitivamente que la existencia de problemas que son difíciles de resolver pero cuyas soluciones son fáciles de verificar coincide con la experiencia del mundo real. [30]
Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que normalmente suponemos. 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 hay un exceso de confianza al creer que P ≠ NP y que los investigadores deberían explorar también pruebas de P = NP. Por ejemplo, en 2002 se hicieron estas declaraciones: [8]
El principal argumento a favor de P ≠ NP es la falta total de avances fundamentales en el área de la búsqueda exhaustiva. Éste es, en mi opinión, un argumento muy débil. El espacio de los algoritmos es muy grande y estamos sólo en el comienzo de su exploración. [...] La resolución del último teorema de Fermat también muestra que cuestiones muy simples sólo pueden resolverse mediante teorías muy profundas.
Estar apegado a una especulación no es una buena guía para la planificación de la investigación. Siempre se deben probar ambas direcciones de cada problema. Los prejuicios han 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.
Cuando se sustituye "tiempo lineal en una máquina de Turing multicinta" por "tiempo polinómico" en las definiciones de P y NP, se obtienen las clases DLIN y NLIN . Se sabe [31] que DLIN≠NLIN.
Una de las razones por las que el problema atrae tanta atención son las consecuencias de las posibles respuestas. Cualquiera de las dos direcciones de resolución haría avanzar enormemente la teoría y quizás también tendría enormes consecuencias prácticas.
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 porque 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 acotado sea pequeño o incluso específicamente conocido. Una prueba no constructiva podría mostrar que existe una solución sin especificar un algoritmo para obtenerla ni un límite específico. Incluso si la prueba es constructiva y muestra un polinomio límite 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 prueba inicial sería de interés principalmente para los teóricos, pero el conocimiento de que las soluciones en tiempo polinómico son posibles seguramente estimularía la investigación de métodos mejores (y posiblemente prácticos) para lograrlas.
Una solución que muestre P = NP podría revolucionar el campo de la criptografía , que depende de que ciertos problemas sean difíciles. Una solución constructiva y eficiente [Nota 2] a un problema NP completo como 3-SAT rompería la mayoría de los criptosistemas existentes, incluidos:
Estos necesitarían modificación o reemplazo con soluciones teóricamente seguras para la información que no supongan P ≠ NP.
También se obtendrían enormes beneficios al hacer manejables muchos problemas que actualmente son matemáticamente intratables. Por ejemplo, muchos problemas de investigación de operaciones son NP-completos, como los 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; [35] hacer que estos problemas se puedan resolver de manera eficiente podría hacer avanzar considerablemente las ciencias de la vida y la biotecnología.
Estos cambios podrían ser insignificantes en comparación con la revolución que causaría en las matemáticas la resolución eficiente de problemas NP-completos. Gödel, en sus primeras reflexiones sobre la complejidad computacional, señaló que un método mecánico que pudiera resolver cualquier problema revolucionaría las matemáticas: [36] [37]
Si realmente existiera una máquina con φ( n ) ∼ k ⋅ n (o incluso ∼ k ⋅ n 2 ), esto tendría consecuencias de la mayor importancia. Es decir, significaría obviamente que, a pesar de la indecidibilidad del Entscheidungsproblem , el trabajo mental de un matemático respecto a preguntas de Sí o No podría ser completamente reemplazado por una máquina. Después de todo, simplemente habría que elegir un número natural n tan grande que cuando la máquina no dé un resultado, no tenga sentido pensar más en el problema.
De manera similar, Stephen Cook (asumiendo no sólo una prueba, sino un algoritmo prácticamente eficiente) dice: [28]
... transformaría las matemáticas al permitir que una computadora encuentre una prueba formal de cualquier teorema que tenga una prueba de una longitud razonable, ya que las pruebas formales pueden reconocerse fácilmente en tiempo polinomial. Los problemas de ejemplo pueden incluir todos los problemas de premios del CMI .
Los investigadores matemáticos pasan sus carreras tratando de demostrar teoremas, y algunas demostraciones han tardado décadas o incluso siglos en encontrarlas 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 garantice encontrar una prueba si existe una prueba de tamaño "razonable" esencialmente 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 prueba: [38]
[...] si imaginas un número M que es finito pero increíblemente grande, como digamos el número 10 ↑ ↑ ↑ ↑ 3 discutido en mi artículo sobre "hacer frente a la finitud", entonces hay una enorme cantidad de algoritmos posibles que no M operaciones bit a bit o de suma o desplazamiento en n bits dados, y es realmente difícil de creer que todos esos algoritmos fallen. Mi punto principal, sin embargo, es que no creo que la igualdad P = NP resulte útil incluso si se prueba, porque tal prueba casi seguramente no será constructiva.
Una prueba de P ≠ NP carecería de los beneficios computacionales prácticos de una prueba de que P = NP, pero representaría un gran avance en la teoría de la complejidad computacional y guiaría investigaciones futuras. Demostraría que muchos problemas comunes no pueden resolverse eficientemente, de modo que la atención de los investigadores puede centrarse en soluciones parciales o soluciones a otros problemas. Debido a la creencia generalizada en P ≠ NP, gran parte de este enfoque de la investigación ya se ha llevado a cabo. [39]
P ≠ NP todavía deja abierta la complejidad del caso 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 del mismo se puedan resolver de manera eficiente. Russell Impagliazzo ha descrito cinco "mundos" hipotéticos que podrían resultar de diferentes soluciones posibles a la cuestión de la complejidad del caso promedio. [40] Estos van desde "Algorithmica", donde P = NP y problemas como SAT se pueden resolver eficientemente en todos los casos, hasta "Cryptomania", donde P ≠ NP y generar casos difíciles de problemas fuera de P es fácil, con tres posibilidades intermedias. reflejando diferentes distribuciones posibles de dificultad en instancias de problemas NP-difíciles. El "mundo" donde P ≠ NP pero todos los problemas en NP son manejables en el caso promedio se denomina "Heurística" en el artículo. Un taller de la Universidad de Princeton en 2009 estudió el estado de los cinco mundos. [41]
Aunque el problema P = NP sigue abierto a pesar de un premio de un millón de dólares y una enorme cantidad de investigación dedicada, los esfuerzos para resolver el problema han dado lugar a varias técnicas nuevas. En particular, algunas de las investigaciones más fructíferas relacionadas con el problema P = NP han demostrado que las técnicas de prueba existentes son insuficientes para responder la pregunta, lo que sugiere que se requieren enfoques técnicos novedosos.
Como evidencia adicional de la dificultad del problema, esencialmente todas las técnicas de prueba conocidas en la teoría de la complejidad computacional caen en una de las siguientes clasificaciones, todas insuficientes para probar 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 que los resultados anteriores no excluyen.
Estas barreras llevan a algunos informáticos a sugerir que el problema P versus NP puede ser independiente de los sistemas de axiomas estándar como ZFC (no se puede probar ni refutar dentro de ellos). Un resultado de independencia podría implicar que P ≠ NP y esto no se puede demostrar en (por ejemplo) ZFC, o que P = NP pero no se puede demostrar en ZFC que algún algoritmo de tiempo polinomial sea correcto. [45] Sin embargo, si el problema es indecidible incluso con suposiciones mucho más débiles que extienden los axiomas de Peano para la aritmética de enteros, entonces existen algoritmos de tiempo casi polinomial para todos los problemas NP. [46] Por lo tanto, suponiendo (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 demostrar la independencia de PA o ZFC con las técnicas actuales no es más fácil que demostrar que todos los problemas NP tienen algoritmos eficientes.
El problema P = NP se puede reformular como ciertas clases de enunciados lógicos, como resultado del trabajo en complejidad descriptiva .
Considere todos los lenguajes de estructuras finitas con una firma fija que incluya una relación de orden lineal . Entonces, todos esos lenguajes en P son expresables en lógica de primer orden con la adición de un combinador de punto mínimo adecuado . Las funciones recursivas se pueden definir con esto y la relación de orden. Siempre que la firma contenga al menos un predicado o función además de la relación de orden distinguida, de modo que la cantidad de espacio necesaria para almacenar tales estructuras finitas sea en realidad polinómica en el número de elementos de la estructura, esto caracteriza precisamente a P.
De manera similar, la NP es el conjunto de lenguajes expresables en la lógica existencial de segundo orden , es decir, la lógica de segundo orden restringida para excluir la cuantificación universal de 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 menor punto fijo no puede?" . [47] La palabra “existencial” puede incluso eliminarse de la caracterización anterior, ya que P = NP si y sólo si P = PH (ya que el primero establecería que NP = co-NP, lo que a su vez implica que NP = PH) .
Ningún algoritmo conocido para un problema NP-completo se ejecuta en tiempo polinómico. Sin embargo, existen algoritmos conocidos para problemas NP-completos en los que si P = NP, el algoritmo se ejecuta en tiempo polinómico 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 polinómico porque su tiempo de ejecución al rechazar instancias no es polinómico. 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 sólo si P = NP:
// Algoritmo que acepta el lenguaje NP-completo SUBSET-SUM. // // este es un algoritmo de tiempo polinómico si y sólo si P = NP. // // "Tiempo polinomial" significa que devuelve "sí" en tiempo polinómico cuando // la respuesta debería ser "sí" y se ejecuta para siempre cuando es "no". // // Entrada: S = un conjunto finito de números enteros // Salida: "sí" si cualquier subconjunto de S suma 0. // Se ejecuta para siempre sin salida en caso contrario. // Nota: "Número de programa M" es el programa obtenido // escribiendo el número entero M en binario, luego // considerando esa cadena de bits como // un programa. Todos los programas posibles pueden // generarse 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 números enteros distintos Y los números enteros están todos en S Y los números enteros suman 0 ENTONCES SALIDA "sí" y DETENER
Este es un algoritmo de tiempo polinómico que acepta un lenguaje NP completo sólo si P = NP. "Aceptar" significa que da respuestas "sí" en tiempo polinómico, pero se le permite ejecutarse para siempre 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 polinómico tiene una longitud de b bits, el algoritmo anterior probará primero con al menos 2 b − 1 programas más.
Un problema de decisión es un problema que toma como entrada alguna cadena w sobre un alfabeto Σ y genera "sí" o "no". Si hay un algoritmo (por ejemplo, una máquina de Turing o un programa de computadora 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, luego decimos que el problema se puede resolver en tiempo polinómico y lo ubicamos en la clase P. Formalmente, P es el conjunto de lenguajes que se pueden resolver mediante una máquina de Turing determinista de tiempo polinómico. Significado,
dónde
y una máquina de Turing determinista de tiempo polinomial es una máquina de Turing determinista M que satisface dos condiciones:
NP se puede definir de manera similar utilizando máquinas de Turing no deterministas (la forma tradicional). Sin embargo, un enfoque moderno utiliza el concepto de certificado y verificador . Formalmente, NP es el conjunto de lenguajes con un alfabeto finito y un verificador que se ejecuta en tiempo polinómico. Lo siguiente define un "verificador":
Sea L un lenguaje sobre un alfabeto finito, Σ.
L ∈ NP si, y sólo si, existe una relación binaria y un entero positivo k tal que se cumplan las dos condiciones siguientes:
Una máquina de Turing que decide L R se llama verificador de L y una y tal que ( x , y ) ∈ R se llama certificado de membresía de x en L .
No todos los verificadores deben ser de tiempo polinomial. Sin embargo, para que L esté en NP, debe haber un verificador que se ejecute en tiempo polinómico.
Dejar
Si un valor de x es compuesto es equivalente a si x es miembro de COMPUESTO. Se puede demostrar que COMPUESTO ∈ NP verificando que satisface la definición anterior (si identificamos los números naturales con sus representaciones binarias).
COMPUESTO también está en P, un hecho demostrado por la invención de la prueba de primalidad AKS . [48]
Hay muchas formas equivalentes de describir la completitud NP.
Sea L un lenguaje sobre un alfabeto finito Σ.
L es NP-completo si, y sólo si, se cumplen las dos condiciones siguientes:
Alternativamente, si L ∈ NP, y hay otro problema NP-completo que puede reducirse en tiempo polinómico a L , entonces L es NP-completo. Esta es una forma común de demostrar que algún problema nuevo es NP completo.
Si bien el problema P versus NP generalmente se considera no resuelto, [49] muchos investigadores aficionados y algunos profesionales han reclamado soluciones. Gerhard J. Woeginger compiló una lista de 62 supuestas pruebas de P = NP de 1986 a 2016, de las cuales 50 eran pruebas de P ≠ NP, 2 eran pruebas de que el problema no se puede demostrar y una era una prueba de que es indecidible. [50] Algunos intentos de resolver P versus NP han recibido breve atención de los medios, [51] aunque estos intentos han sido refutados.
La película El viajante , del director Timothy Lanzone, es la historia de cuatro matemáticos contratados por el gobierno estadounidense para resolver el problema P versus NP. [52]
En el sexto episodio de la séptima temporada de Los Simpson , " La casa del árbol del terror VI ", la ecuación P = NP se ve poco después de que Homero tropieza accidentalmente con la "tercera dimensión". [53] [54]
En el segundo episodio de la temporada 2 de Elementary , "Solve for X", Sherlock y Watson investigan los asesinatos de matemáticos que intentaban resolver P versus NP. [55] [56]
Este problema se refiere a 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).
Supongamos que está organizando alojamiento para un grupo de cuatrocientos estudiantes universitarios. Las plazas son limitadas y sólo cien estudiantes recibirán plaza en el dormitorio. Para complicar las cosas, el Decano le ha proporcionado una lista de pares de estudiantes incompatibles y le ha solicitado que ningún par de esta lista aparezca en su elección final. Este es un ejemplo de lo que los informáticos llaman un problema NP...
