Nothing Special   »   [go: up one dir, main page]
Saltar ao contido

P versus NP

Na Galipedia, a Wikipedia en galego.
(Redirección desde «Clases de complexidade P e NP»)
Diagrama das clases de complexidade considerando que P ≠ NP. A existencia de problemas NP fóra de P e de NP-completo, baixo esta hipótese, estableceuna o teorema de Ladner.[1]

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 2n-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

[editar | editar a fonte]

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

[editar | editar a fonte]

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

[editar | editar a fonte]

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

[editar | editar a fonte]
  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. 
  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.
  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. 
  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. 
  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. 

Véxase tamén

[editar | editar a fonte]

Bibliografía

[editar | editar a fonte]

Ligazóns externas

[editar | editar a fonte]
Traído desde «https://gl.wikipedia.org/w/index.php?title=P_versus_NP&oldid=6650203»