miniatura|250px|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.R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site. 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", e está considerado como o problema aberto máis importante neste eido. É 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".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.
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 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 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. 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, 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.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. 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.
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.
Solucións supostas A pesar de que o problema P versus NP está xeralmente aceptado como sen resolver, moitos investigadores afeccionados ou profesionais reclaman ter solucións. Gerhard J. Woeginger ten unha listaxe, 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. A demostración foi revisada por estudosos,Science News, "Crowdsourcing peer review" e Neil Immerman, experto na área, sinalou dous erros posiblemente fatais na demostración. En setembro de 2010, informouse que Deolalikar estaba a traballar nunha expansión detallada do seu intento de demostración. 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.Gödel’s Lost Letter and P=NP, Update on Deolalikar’s Proof that P≠NP Esta valoración deu lugar a un artigo en The New Yorker en maio de 2013 que consideraba o intento "completamente desacreditado".
Notas
Véxase tamén Bibliografía
Online drafts
Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible . Princeton University Press. Princeton, NJ (2013) Ligazóns externas The Clay Mathematics Institute Millennium Prize Problems
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
Categoría:Matemáticas