P versus NP
From Wikipedia, the free encyclopedia
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.