El 10 de novembre vaig llançar la pregunta “Que vol dir complexitat P i NP?” per als que volguessin invitacions a google wave.

La teoria de complexitat computacional forma 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 instruccions calen per resoldre el problema) i espai (quanta capacitat es necessita per resoldre el problema).

Un problema de molta complexitat de computació i que s’ha estudiat molt la seva optimització és el del viatjant de comerç

Donat un conjunt de llocs o ciutats, es tracta de trobar l’ordre a seguir per tal de tal que el camí fet pel viatjant de comerç des del punt de partida fins al punt d’arribada sigu el més curt possible.

Un problema de decisió és un problema que agafa com a entrada una cadena i dóna com a sortida una resposta de tipus SI o NO. Si existeix un algorisme que és capaç de donar la resposta correcta per qualsevol cadena d’entrada de longitud n en com a màxim c*nk 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.

Exemples de càlcul de complexitat

• Extreure qualsevol element d’un vector. La indexació d’un vector o array porta el mateix temps sigui quin sigui l’índex que es vulgui buscar. Per tant és una operació de complexitat constant O(1).
• Buscar en un diccionari té una complexitat logarítmica. Es pot iniciar la cerca d’una paraula per la meitat del diccionari. Immediatament, se sap si s’ha trobat la paraula o, en cas contrari, en quina de les dues mitats s’ha de repetir el procés (és un procés recursiu) fins a trobar el resultat. A cada (sub)cerca, el problema (les pàgines on pot estar la paraula) s’ha reduït a la mitat, lo que es correspon amb la funció logarítmica. Aquest procediment de cerca (conegut com cerca binaria en una estructura ordenada té una complexitat logarítmica O(ln n).
• El procés més habitual per ordenar conjunts d’elements té complexitat quadràtica. El procediment consisteix a crear una col·lecció buida d’elements. Se li afegeix, en ordre, el menor element del conjunt original que encara no s’hagi triat, el que implica fer un recorregut complet del conjunt original (O(n), essent n el nombre d’elements del conjunt). Aquest recorregut sobre el conjunt original es realitza fins que tots els seus elements estan a la seqüència de resultat. Es pot veure que s’ha de fer n seleccions (s’ordena tot el conjunt) cada una amb un cost n d’execució: el procediment és d’orde quadràtica O(n²). De tota manera hi ha diversos algorismes d’ordenació amb millors resultats.

Turing va construir un model formal de computador, la màquina de Turing, i va demostrar que existien problemes que una màquina no podia resoldre.

La màquina de Turing (MTD) consta d’un capçal lector/escriptor i una cinta infinita en la que el capçal llegix el contingut, esborra el contingut anterior i escriu un nou valor. Les operacions que es poden realitzar en aquesta màquina es limiten a:  avançar el capçal lector/escriptor cap a la dreta o cap a l’esquerra;
El còmput és determinat a partir d’una taula d’estats de la forma:

(estat, valor) => (nou estat, nou valor, direcció)

La classe P consisteix en els problemes en que les seves solucions poden ser trobades en un temps polinòmic en una màquina de Turing.

On una màquina de Turing té un sol “camí de computació” a seguir, una màquina no determinista té un “arbre de computació”. En les màquines no deterministes la funció de transició és una funció multivaluada sobre els estats i els símbols. Aquí caldria imaginar-se que la màquina “es divideix” en diverses còpies, i cada una segueix una de les possibles transicions.

La classe NP consisteix en els problemes en que les seves solucions poden ser trobades en un temps polinòmic en una màquina no determinista, i per els quals la seva solució positiva es pot verificar en relació a la mida de l’entrada del problema en una màquina de Turing.

La dificultat dels problemes NP és trobar la resposta de forma eficient, donada una forma eficient (en temps polinòmic) de verificar-la un cop trobada.

Es creu que P ≠ NP
En informàtica es parteix de la base que P ≠ NP, ja que no s’ha trobat un algorisme de temps polinomial per un problema NP-complet. A demés si P = NP implicaria conseqüències que es creuen falses. Intenta demostrar que P és igual a NP. L’institut Clay et donaria 1 mil·lió de dòlars.

Problemes “intractables” i NP-Complets
Tot i que el processament de les màquines de Turing són més simples que les no Deterministes no vol dir que, per la mateixa entrada, un problema de la classe P tardi menys que un de la classe NP. Exemple: Un problema que requereix 10^1000n en temps i és a la classe P és polinòmic en el temps, però intractable a la pràctica. En canvi hi ha problemes que tot i tenir un temps en funció exponencial (NP) són tractables a la pràctica si l’entrada es prou petita.

Els problemes que tenen solucions en temps polinòmics són solubles per més que uns quants valors. Els problemes poc escalables son els “EXPTIME-complet”. Assumint P ≠ NP, els problemes NP-Complet són intractables.