P versus NP

De Viquipèdia

Diagrama de classes de complexitat mostrant que P ≠ NP. Si P = NP, llavors totes tres classes son 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 polinomial al tamany de les entrades; la classe NP la formen aquells problemes de decisió els quals la seva solució positiva es pot verificar en un temps polinomial 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 es igual a NP?

L'institut Clay ofereix un mil·lió 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 mes durs dels NPs. Més acuradament, qualsevol problema NP, mitjançant una transformació eficient (de tipus polinomial en el temps), es pot expressar com un problema NP-complet. D'aquesta forma, si algú troba una solució eficient (en termes polinomials ) per qualsevol problema NP-complet, llavors tots els problemes NP poden ser solucionats eficientment i a més ha de pertanyer al grup P, i provant per tant que P = NP. (Veure 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 SI/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 SI, tot i que pot costar un cert temps per trobar un subconjunt que ho faci - i si el el conjunt és gran, es pot tardar molt de temps a trobar-lo. Per altre banda, si algú afirma que la resposta es "SI, perquà {-2, -3, -10, 15} sumen zero", llavors podem comprovar-ho amb molt poques operacions simples. Verificar que un conjunt suma zero es 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 polinomial) i és per això que aquest problema pertany a la classe NP.

La restricció SI/NO als problemes no dóna cap diferència; inclús si es permeten respostes mes complicades, el problema resultant es equivalent. (Veure classes FP i NFP)

[edita] Definició formal

Més acuradament, un problema de decisió és un problema que agafa com a entrada alguna cadena i dóna com a sortida una resposta de tipus SI 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 polinomial 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 es una cadena d'entrada pel nostre problema de decisió, i una cadena C que es un "certificat proposat", i que aquest A produeix una resposta SI/NO en com a màxima c*n^k passes (on n es la longitud de w, i ni c ni k depenen de w). Suposem a demés que

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

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. (Veure que la abreviatura de NP ve de "No determinista Polinomial" i no de "No-Polinomial".)

[edita] 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 polinomial. Els problemes NP-complet son 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 polinomial. 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. Desafortunadament, s'ha demostrat que molts problemes importants són NP-complet i no s'ha trobat un sol algorisme polinomial per cap d'ells.

[edita] 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 enlloc de l'entrada normal), se sap que son EXPTIME-complets. Per això, es pot demostrar que P EXPSPACE, aquests problemes estan fora de P, i requereixen més que temps polinomial. De fet, pels 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 al 1974 que qualsevol algorisme que decideixi la veritat de afirmacions Presburger te un temps d'execució d'almenys on c és una constant i n es 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.

[edita] 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 a la practica, 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 altre 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 provat que problemes de tipus P requereixen d'exponents enormes (vegeu teorema del temps jeràrquic). En canvi, un problema amb temps 2^n/1000 no pertany a P, però es 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ò en rares ocasions una instància del problema pot necessitar 2ⁿ. Aquest problema té un temps polinomial, 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 pogui 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 (Vegeu RP i BPP). Inclús 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 pertànyer 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 que les classes matemàtiques P' i NP són iguals.

[edita] 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 polinomial 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.