P versus NP

La teoria de complexitat computacional és part de la teoria de la computació, que estudia els recursos necessaris durant el càlcul per resoldre un problema donat. Els recursos més habituals són temps (quantes passes calen per resoldre el problema) i espai (quanta memòria es necessita per resoldre el problema).

En aquesta teoria, la classe P consisteix en tots els problemes de decisió que poden ser resolts en una màquina seqüencial determinista en un espai de temps que és polinòmic respecte la mida de les entrades; la classe NP la formen aquells problemes de decisió els quals la seva solució positiva es pot verificar en un temps polinòmic donada la informació adient, o equivalentment, les seves solucions poden ser trobades en un temps polinòmic en una màquina no determinista. Donat això, la qüestió que queda oberta és sobre la relació entre aquestes dues classes:

P és igual a NP?

És un dels problemes del mil·lenni, i l'Institut Clay de Matemàtiques ofereix un milió de dòlars a qui ho resolgui.^[1]

Un paper important en aquesta discussió el té el conjunt dels problemes NP-complets, que es poden descriure com els problemes més durs dels NPs. Més acuradament, qualsevol problema NP, mitjançant una transformació eficient (de tipus polinòmic en el temps), es pot expressar com un problema NP-complet. D'aquesta forma, si algú troba una solució eficient (en termes polinòmics) per qualsevol problema NP-complet, llavors tots els problemes NP poden ser solucionats eficientment i a més ha de pertànyer al grup P, i es demostraria per tant que P = NP. (Vegeu NP-complet per la definició exacta). La majoria de científics en Informàtica creuen que la relació entre les classe P, NP i NP-complet és com es mostra a la figura, amb les classes P i NP-complet disjuntes.

En essència, la qüestió P = NP pregunta: si una solució positiva per un problema de SÍ/NO pot ser verificada ràpidament, poden calcular-se igual de ràpidament les respostes? Es presenta a continuació un exemple: Donat un conjunt d'enters, existeix algun subconjunt que sumi 0? Per exemple, donat el conjunt {-2, -3, 8, 15, -10} existeix algun subconjunt que doni 0? La resposta es SÍ, tot i que pot costar un cert temps per trobar un subconjunt que ho faci - i si el conjunt és gran, es pot tardar molt de temps a trobar-lo. Per altra banda, si algú afirma que la resposta és "SÍ, perquè {-2, -3, -10, 15} sumen zero", llavors podem comprovar-ho amb molt poques operacions simples. Verificar que un conjunt suma zero és molt més ràpid que trobar el subconjunt de la primera solució. La informació necessària per verificar una solució positiva s'anomena certificat. Podem concloure que donat el certificat adient, respostes positives al nostre problema es poden verificar ràpidament (en temps polinòmic) i és per això que aquest problema pertany a la classe NP.

La restricció SÍ/NO als problemes no dona cap diferència; inclús si es permeten respostes més complicades, el problema resultant és equivalent.

Es considera que aquest problema és el problema obert més important en les ciències de la computació.^[2] A més de ser un problema important en teoria de la computació, una demostració en qualsevol dels dos sentits tindria implicacions molt profundes en les matemàtiques, en la criptografia, en la recerca algorísmica, en la intel·ligència artificial, en la teoria de jocs, en el processament multimèdia, en la filosofia, en l'economia i en molts altres camps.^[3]