P versus NP

O problema P versus NP é un dos principais problemas sen resolver na teoría da computación. Informalmente, a cuestión é se todo problema cunha solución que pode ser verificada rapidamente por un computador, tamén pode ser resolta rapidamente por un computador.

As primeiras nocións do problema foron discutidas na década de 1950 en cartas de John Forbes Nash, Jr. á National Security Agency, e de Kurt Gödel a John von Neumann. O enunciado preciso foi introducido en 1971 por Stephen Cook no seu artigo "The complexity of theorem proving procedures",^[2] e está considerado como o problema aberto máis importante neste eido.^[3] É ademais un dos problemas do milenio, seleccionados polo Clay Mathematics Institute, que ofrece un premio dun millón de dólares á primeira solución correcta.

O termo informal “rapidamente” refírese á existencia dun algoritmo que resolva a tarefa nun tempo polinómico, é dicir, nun tempo que varía de forma polinómica en función do tamaño da entrada do algoritmo (oposto, por exemplo, ao tempo exponencial). A clase xeral de cuestións para as que un algoritmo ofrece unha resposta nun tempo polinómico denomínase "clase P" ou simplemente "P". Para algunhas cuestións, non se coñece xeito de atopar a resposta rapidamente, mais se se proporciona información sobre cal é esa resposta é posible verificala rapidamente. Esta clase de problemas para os que a solución pode verificarse en tempo polinómico denomínase NP, que se refire a "tempo polinómico non determinista".^[4]

Considérese o problema da suma de subconxuntos, exemplo dun problema que é fácil de verificar pero cunha resposta difícil de calcular. Dado un conxunto de enteiros, existe algún subconxunto non baleiro que sume 0? A resposta “si, porque o conxunto {−2, −3, −10, 15} suma cero” pode ser verificada rapidamente con tres sumas. Non se coñece ningún algoritmo que atope este subconxunto en tempo polinómico (si o hai en tempo exponencial, que consiste en 2ⁿ-n-1 intentos), pero o algoritmo existe se P = NP; xa que logo este problema está en NP (rapidamente verificable) mais non necesariamente en P (rapidamente resoluble).

Unha resposta P = NP determinaría que os problemas que poden ser verificados en tempo polinómico, poden tamén ser resoltos en tempo polinómico. Pola contra, P ≠ NP, implicaría que hai problemas en NP (como os problemas NP-completos) que son máis complexos de calcular que de verificar: non poderían resolverse en tempo polinómico, mais a resposta podería verificarse en tempo polinómico.

Á parte de ser un importante problema en teoría da computación, unha proba en calquera sentido tería importantes implicacións en matemáticas, criptografía, busca de algoritmos, intelixencia artificial, teoría de xogos, procesos multimedia, filosofía ou economía.

Historia

Aínda que o problema P versus NP foi definido formalmente en 1971, houbo cuestións previas que incluían o problema, a dificultade de probalo e as consecuencias potenciais. En 1955 o matemático John Nash escribiu unha carta á NSA na que especulaba que descifrar un código suficientemente complexo requiriría un tempo exponencial en función da lonxitude da clave.^[5] Se se probase (e Nash era escéptico) implicaría o que hoxe se chamaría P ≠ NP, xa que unha clave proposta pode ser facilmente verificada en tempo polinomial. Outra mención ao problema subxacente aparece nunha carta de 1956 de Kurt Gödel a John von Neumann. Gödel preguntaba se un teorema (que agora se sabe que é co-NP-completo) podía ser resolto en tempo cuadrático ou tempo linear,^[6] e sinalaba unha das consecuencias máis importantes nese caso, que sería o descubrimento de que as demostracións matemáticas podían ser automatizadas.

Contexto

A relación entre as clases de complexidade P e NP estúdase na teoría da complexidade computacional, parte da teoría da computación que traballa cos recursos que se requiren durante o cálculo para resolver un problema dado. Os recursos máis comúns son o tempo (cantos pasos se precisan para resolver un problema?) e o espazo (canta memoria se precisa para resolver un problema?).

Nesta análise, requírese un modelo de computador para o que se vai analizar o tempo. Adoita considerarse que estes modelos son deterministas (dado o estado actual do computador e algunha entrada, só é posible que o computador realice unha acción) e secuenciais (realiza accións unha despois doutra).

Nesta teoría, a clase P consiste en todos aqueles problemas de decisión que poden resolverse nunha máquina determinista secuencial nunha cantidade de tempo que é polinómica en función do tamaño da entrada; a clase NP consiste en todos os problemas de decisión con solucións positivas que poden ser verificadas en tempo polinómico dada a información correcta, ou equivalentemente, con solucións que poden ser atopadas en tempo polinómico nunha máquina non determinista.^[7] Claramente, P ⊆ NP. A maior pregunta aberta na ciencia computacional teórica refírese á relación entre estas dúas clases:

É P igual a NP?

Nunha enquisa realizada en 2002 entre 100 estudosos, 61 crían que a resposta é non, 9 que é si e 22 estaban indecisos; 8 crían que a cuestión pode ser independente dos axiomas aceptados na actualidade e polo tanto imposible de probar en calquera sentido.^[8]

En 2012, 10 anos despois, repetiuse a mesma enquisa preguntando a 151 investigadores: 126 (83%) crían que a resposta é non, 12 (9%) crían que a resposta é si, 5 (3%) crían que a cuestión é independente dos axiomas aceptados na actualidade e 8 (5%) dixeron que non sabían, non lles importaba ou non querían que a resposta fose si ou que o problema fose resolto.^[9]

Solucións supostas

A pesar de que o problema P versus NP está xeralmente aceptado como sen resolver,^[10] moitos investigadores afeccionados ou profesionais reclaman ter solucións. Gerhard J. Woeginger ten unha listaxe,^[11] que en 2016 contiña 62 supostas probas de P = NP e 50 de P ≠ NP. En agosto de 2010 unha proba de P ≠ NP, de Vinay Deolalikar, investigador en HP Labs, recibiu atención en Internet e na prensa, tras ser descrita como "[parece] ser un intento relativamente serio" de dos especialistas destacados.^[12] A demostración foi revisada por estudosos,^[13]^[14] e Neil Immerman, experto na área, sinalou dous erros posiblemente fatais na demostración.^[15] En setembro de 2010, informouse que Deolalikar estaba a traballar nunha expansión detallada do seu intento de demostración.^[16] Non obstante, as opinións expresadas por varios importantes científicos computacionais teóricos indican que a demostración nin é correcta nin é un avance significativo para entender o problema.^[17] Esta valoración deu lugar a un artigo en The New Yorker en maio de 2013 que consideraba o intento "completamente desacreditado".^[18]

Notas

↑ R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
↑ Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.
↑ Fortnow, Lance (2009). "The status of the P versus NP problem". Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186.
↑ Unha máquina de Turing non determinista pode moverse a un estado que non está determinado polo estado previo. Esta máquina podería resolver un problema NP nun tempo polinómico caendo na resposta correcta (por azar), verifícandoa entón. Estas máquinas non son prácticas para resolver problemas realistas pero poden empregarse como modelos teóricos.
↑ NSA (2012). "Letters from John Nash" (PDF). Arquivado dende o orixinal (PDF) o 07 de agosto de 2017. Consultado o 07 de agosto de 2017.
↑ Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101–107.
↑ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
↑ William I. Gasarch (xuño de 2002). "The P=?NP poll." (PDF). SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. Consultado o 29-122008.
↑ William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT News 74.
↑ John Markoff (8-10-2009). "Prizes Aside, the P-NP Puzzler Has Consequences". The New York Times.
↑ Gerhard J. Woeginger. "The P-versus-NP page". Consultado o 25-5-2014.
↑ Markoff, John (16-8-2010). "Step 1: Post Elusive Proof. Step 2: Watch Fireworks.". The New York Times. Consultado o 20-9-2010.
↑ Polymath Project wiki. "Deolalikar's P vs NP paper".
↑ Science News, "Crowdsourcing peer review"
↑ Dick Lipton (12-8-2010). "Fatal Flaws in Deolalikar's Proof?".
↑ Dick Lipton (15-9-2010). "An Update on Vinay Deolalikar's Proof". Consultado o 31-12-2010.
↑ Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP
↑ Alexander Nazaryan (2-5-2013). "A Most Profound Math Problem". Consultado o 1-5-2014.

Véxase tamén

Bibliografía

Fraenkel, A. S.; Lichtenstein, D. (1981). "Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.". Lecture Notes in Computer Science: 278–293. doi:10.1007/3-540-10843-2_23.
Garey, Michael; Johnson, David (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. ISBN 0-7167-1045-5.
Goldreich, Oded (2010). P, Np, and Np-Completeness. Cambridge: Cambridge University Press. ISBN 978-0-521-12254-2. Online drafts
Immerman, N. (1987). "Languages which capture complexity classes". SIAM Journal of Computing 16 (4): 760–778. doi:10.1137/0216051.
Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 0-262-03293-7.
Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 0-201-53082-1.
Fortnow, L. (2009). "The Status of the P versus NP problem". Communications of the ACM 52 (9): 78. doi:10.1145/1562164.1562186.
Fortnow, L.; Gasarch, W. "Computational complexity".
Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible ISBN 9780691156491. Princeton University Press. Princeton, NJ (2013)

Ligazóns externas

The Clay Mathematics Institute Millennium Prize Problems
"The Clay Math Institute Official Problem Description" (PDF). Arquivado dende o orixinal (PDF) o 04 de setembro de 2015. Consultado o 07 de agosto de 2017. (118 KB)
Gerhard J. Woeginger. The P-versus-NP page. Listaxe de ligazóns a varias solución propostas ao problema. Algunhas afirman que P é igual a NP e outras o contrario. Probablemente todas estas solución sexan incorrectas.
Scott Aaronson 's Shtetl Optimized blog: Reasons to believe, listaxe de xustificacións para crer que P ≠ NP

[Ladner75-1] R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.

[2] Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.

[3] Fortnow, Lance (2009). "The status of the P versus NP problem". Communications of the ACM 52 (9): 78–86. doi:10.1145/1562164.1562186.

[Note-4] Unha máquina de Turing non determinista pode moverse a un estado que non está determinado polo estado previo. Esta máquina podería resolver un problema NP nun tempo polinómico caendo na resposta correcta (por azar), verifícandoa entón. Estas máquinas non son prácticas para resolver problemas realistas pero poden empregarse como modelos teóricos.

[5] NSA (2012). "Letters from John Nash" (PDF). Arquivado dende o orixinal (PDF) o 07 de agosto de 2017. Consultado o 07 de agosto de 2017.

[6] Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science 38: 101–107.

[7] Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.

[poll-8] William I. Gasarch (xuño de 2002). "The P=?NP poll." (PDF). SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. Consultado o 29-122008.

[poll2-9] William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT News 74.

[10] John Markoff (8-10-2009). "Prizes Aside, the P-NP Puzzler Has Consequences". The New York Times.

[11] Gerhard J. Woeginger. "The P-versus-NP page". Consultado o 25-5-2014.

[NYT2010-12] Markoff, John (16-8-2010). "Step 1: Post Elusive Proof. Step 2: Watch Fireworks.". The New York Times. Consultado o 20-9-2010.

[13] Polymath Project wiki. "Deolalikar's P vs NP paper".

[14] Science News, "Crowdsourcing peer review"

[15] Dick Lipton (12-8-2010). "Fatal Flaws in Deolalikar's Proof?".

[16] Dick Lipton (15-9-2010). "An Update on Vinay Deolalikar's Proof". Consultado o 31-12-2010.

[17] Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP

[18] Alexander Nazaryan (2-5-2013). "A Most Profound Math Problem". Consultado o 1-5-2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]