P versus NP

Diagrama de classes de complexitat suposant que P ≠ NP. Si P = NP, llavors totes tres classes serien iguals.

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.

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ó. 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.

Història

La formulació precisa del problema P versus NP va ser introduïda l'any 1971 per Stephen Cook en el seu article deminal "La complexitat de procediments de demostració de teoremes" (i independentment per Leònid Levin l'any 1973).

Tot i que el problema de P versus NP va ser formalment definit l'any 1971, hi va haver derivades del problema prèvies, la dificultat de demostrar-la, i les conseqüències potencials. L'any 1955, el matemàtic John Nash va escriure una carta a la NSA, en què especulava que desxifrar un codi suficientment complex requeriria un temps exponencial respecte de la longitud de la clau. Si es demostrava (i Nash n'era en efecte escèptic), això implicaria el que avui en dia s'anomena P ≠ NP, ja que una clau proposada es pot verificar fàcilment en un temps polinòmic. Una altra menció del problema subjacent es va fer en una carta de 1956 escrita per Kurt Gödel a John von Neumann. Gödel pregunta si demostrar teoremes (que avui se sap que és un problema co-NP-complet) es podia resoldre en un temps quadràtic o lineal, i va observa una de les conseqüències més importants —que, de ser així, llavors el descobriment de demostracions matemàtiques es podria automatitzar.

Definició formal

Més acuradament, un problema de decisió és un problema que agafa com a entrada alguna cadena i dona com a sortida una resposta de tipus SÍ o NO. Si existeix un algorisme (o Màquina de Turing, o un programa) que és capaç de donar la resposta correcta per qualsevol cadena d'entrada de longitud n en com a màxim c*n^k passes, on k i c són constants independents de la longitud de la cadena, llavors diem que el problema es pot resoldre en temps polinòmic i per tant pertany a la classe P. Intuïtivament, es poden pensar els problemes P com aquells que es poden resoldre raonablement ràpids.

Suposem ara un algorisme A(w,C) que agafa dos arguments, una cadena w que és una cadena d'entrada pel nostre problema de decisió, i una cadena C que és un "certificat proposat", i que aquest A produeix una resposta SÍ/NO en com a màxima c*n^k passes (on n és la longitud de w, i ni c ni k depenen de w). Suposem a més que

w és una instància SÍ del problema de decisió si i només si existeix C tal que A(w,C) retorna SÍ.

Llavors podem dir que el problema es pot resoldre en un "temps polinòmic no determinista", i per tant s'afegeix a la classe NP. Podem pensar en l'algorisme A com un verificador del certificat proposat que corre raonablement ràpid. (Vegeu que l'abreviatura de NP ve de "No determinista Polinòmic" i no de "No-Polinòmic".)

NP-complet

Per atacar la qüestió P = NP, és força útil el concepte NP-complet. Informalment, els problemes NP-complets són els problemes més "durs" dels NPs en el sentit que molt probablement no pertanyin a la classe P. Els problemes NP-hard són aquells en els que qualsevol problema NP es pot transformar en temps polinòmic. Els problemes NP-complet són aquells problemes NP-hard que estan a NP. Per exemple, la versió del problema de decisió anomenada el problema del viatjant es NP-complet. Per tant qualsevol instància de qualsevol problema a NP es pot transformar mecànicament en una instància del problema del viatjant en temps polinòmic. I per tant, si el problema del viatjant passés a ser un problema P, llavors P = NP!. El problema del viatjant és un dels problemes NP-complet. Si algun problema NP-complet està a P, llavors seguiria que P = NP. Malauradament, s'ha demostrat que molts problemes importants són NP-complets i no s'ha trobat cap algorisme polinòmic per resoldre'ls.

Problemes més complexos

Encara que no se sap si P = NP, es coneixen problemes que estan fora de P. Un nombre de succtinct problems (problemes que operen amb una descripció computacional de l'entrada en lloc de l'entrada normal), se sap que són EXPTIME-complets. Per això, es pot demostrar que P $\subset$EXPSPACE, aquests problemes estan fora de P, i requereixen més que temps polinòmic. De fet, pel teorema del temps jeràrquic, aquests problemes no es poden resoldre amb res menor que temps exponencial.

El problema de decidir la veritat d'una afirmació en aritmètica Presburger és encara més dur. Fischer i Rabin van provar el 1974 que qualsevol algorisme que decideixi la veritat d'afirmacions Presburger té un temps d'execució d'almenys $2^{2^{cn}}$ on c és una constant i n és la longitud de l'afirmació Presburger. De fet, es coneix que aquest problema necessita més temps que no pas un temps exponencial. Problemes encara més durs són problemes indecidibles, com ara el problema de la parada. Aquests problemes no es poden resoldre per un cas general en un temps finit.

Realment és P tractable?

En les discussions anteriors, s'ha assumit que P vol dir "senzill" i que "no a P" vol dir "difícil". Aquesta assumpció és comú i bàsicament correcte en teoria de la complexitat, però no sempre és veritat en la pràctica, per les següents raons:

• Ignora els factors constants. Un problema que requereix 10¹⁰⁰⁰n en temps és a la classe P (és linear en el temps), però és totalment intractable a la pràctica. Per altra banda, un problema que el seu temps és de l'ordre 10^-100002ⁿ no pertany a P (té un temps exponencial), però és perfectament tractable per valors de n fins a milers.
• Ignora el valor dels exponents. Un problema amb temps n¹⁰⁰⁰ està dins P, però és intractable. S'ha demostrat que problemes de tipus P requereixen exponents enormes (pel teorema del temps jeràrquic). En canvi, un problema amb temps 2^n/1000 no pertany a P, però és tractable per nombres raonablement grans de n.
• Només es considera el pitjor cas. Pot succeir que un problema real la majoria de cops es pugui resoldre en temps n, però que excepcionalment una instància del problema pugui necessitar 2ⁿ. Aquest problema té un temps polinòmic, però el pitjor cas és exponencial, i per tant el problema no pertany a P.
• Només es consideren solucions deterministes. Pot existir un problema que es pugui solucionar ràpidament si s'accepta un cert marge d'error, però una resposta correcta és molt més difícil d'obtenir. Aquest problema no pertany a P tot i que a la pràctica es pot resoldre ràpidament. De fet, aquesta aproximació és habitual a l'hora d'atacar problemes NP que es desconeix si pertanyen a P. Fins i tot si P = BPP, com molts investigadors creuen, habitualment és més senzill trobar algorismes probabilístics.
• Nous models de computació com ara els computadors quàntics pot ser que resolguin ràpidament problemes que es desconegui si pertanyen a P; tanmateix, cap dels problemes que se sap que poden resoldre és NP-hard. Cal notar també que les definicions de P i NP venen donades en termes de la computació clàssica com són les màquines de Turing. Així i tot, inclús si fos descobert un algorisme per un computador quàntic per resoldre eficientment un problema NP-hard, només s'hauria trobat una manera física de resoldre el problema ràpidament, però no una prova de què les classes matemàtiques P' i NP són iguals.

Perquè es creu que P ≠ NP ?

La majoria d'informàtics creuen que P ≠ NP. La raó principal per aquesta creença és que després de dècades d'estudiar aquests problemes, ningú ha estat capaç de trobar un algorisme amb temps polinòmic per un problema NP-hard. A més, aquests algorismes ja es buscaven molt abans que es conegués el concepte de NP-complet (els 21 NP-complet problemes de Karp). Per altra banda, el resultat P = NP implicaria estranyes conseqüències que es creuen falses, com ara que NP = co-NP i P = PH.

També de forma intuïtiva es pot dir que l'experiència del món real ens diu que existeixen problemes difícils de resoldre però les solucions dels quals són fàcils de verificar.

Bibliografia complementària

• Cormen, Thomas. Introduction to Algorithms. Cambridge: MIT Press, 2001. ISBN 978-0-262-03293-3. 
• Garey, Michael; Johnson, David. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company, 1979. ISBN 978-0-7167-1045-5. 
• Goldreich, Oded. P, NP, and NP-Completeness. Cambridge: Cambridge University Press, 2010. ISBN 978-0-521-12254-2.  Online drafts
• Immerman, N. «Languages that Capture Complexity Classes». SIAM Journal on Computing, 16, 4, 1987, pàg. 760–778. DOI: 10.1137/0216051.
• Papadimitriou, Christos. Computational Complexity. Boston: Addison-Wesley, 1994. ISBN 978-0-201-53082-7.