Complexitat computacional

La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema. Els recursos comunament estudiats són el temps (nombre de passos d'execució d'un algorisme per resoldre un problema) i l'espai (quantitat de memòria utilitzada per soldre un problema). Poden estudiar-se igualment altres paràmetres, com el nombre de processadors necessaris per resoldre el problema en paral·lel. La teoria de la complexitat difereix de la teoria de la computabilitat en què aquesta última s'ocupa de la factibilitat d'expressar problemes com algorismes efectius sense tenir en compte els recursos necessaris per aconseguir-ho.

Els problemes que tenen una solució amb ordre de complexitat lineal són els problemes que es resolen en un temps que es relaciona linealment amb la seva mida.

Avui en dia les màquines resolen problemes mitjançant algorismes que tenen com a màxim una complexitat o cost computacional polinòmic, és a dir, la relació entre la mida del problema i el seu temps d'execució és polinòmic. Aquests són els problemes agrupats en el conjunt P. Els problemes amb cost factorial o combinatori estan agrupats en el conjunt NP. Aquests problemes no tenen una solució pràctica, és a dir, una màquina no pots resoldre'ls en un temps raonable.

Presentació

Un problema donat pot veure's com un conjunt de preguntes relacionades, on cada pregunta es representa per una cadena de caràcters de mida finita. Per exemple, el problema FACTORITZAR es descriu com: Donat un enter escrit en notació binaria, retornar tots els factors primers d'aquest nombre. Una pregunta sobre un enter específic s'anomena una instància. Per exemple, "Trobar els factors primers del nombre 15" és una instància del problema FACTORITZAR.

La complexitat en temps d'un problema és el nombre de passes que calen per resoldre una instància d'un problema, a partir de la mida de l'entrada. Usant l'algorisme més eficient disponible. Intuïtivament, si es pren una instància com entrada de longitud n que pot resoldre's en n² passes, es diu que aquest problema té una complexitat en temps de n². Per descomptat, el nombre exacte de passes depèn de la màquina amb la que s'implementa, del llenguatge usat i d'altres factors. Per a no haver de parlar del cost exacte del càlcul s'usa la notació O. Quan un problema té un cost en temps O(n²) en una configuració de computador i llenguatge donats, aquest cost serà el mateix en tots els computadors, de manera que aquesta notació generalitza la noció de cost independentment de l'equip utilitzat.

Exemples

• 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 a 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²). Cal aclarir que hi ha diversos algorismes d'ordenació amb millors resultats.

Problemes de decisió

La major part dels problemes en teoria de la complexitat tenen a veure amb els problemes de decisió, que corresponen a poder donar una resposta positiva o negativa a un problema donat. Per exemple, el problema ES-PRIMER es pot descriure com: Donat un enter, respondre si aquest nombre és primer o no. Un problema de decisió és equivalent a un llenguatge formal, que és un conjunt de paraules de longitud finita en un llenguatge donat. Per un problema de decisió donat, el llenguatge equivalent és el conjunt d'entrades per al qual la resposta és positiva.

Els problemes de decisió són importants perquè quasi tot problema es pot transforma en un problema de decisió. Per exemple, el problema CONTÉ-FACTORS descrit com: Donats dos enters n i k, decidir si n té algun factor menor que k. Si es pot resoldre CONTÉ-FACTOR amb una certa quantitat de recursos, la seva solució es pot utilitzar per resoldre FACTORITZAR amb els mateixos recursos, realitzant una cerca binaria sobre k fins a trobar el factor més petit de n, llavors es pot dividir aquest factor i es repeteix el procés fins a trobar tots els factors.

En teoria de la complexitat, generalment es distingeix entre solucions positives i negatives. Per exemple, el conjunt NP es defineix com el conjunt dels problemes on les respostes positives es poden verificar molt ràpidament (amb temps polinòmic). El conjunt Co-P és el conjunt de problemes on les respostes negatives es poden verificar ràpidament. El prefix "Co" abrevia "complement". El complement d'un problema és aquell on les respostes positives i negatives estan bescanviades, com entre ÉS-COMPOST i ÉS-PRIMER.

Un resultat important en teoria de la complexitat és el fet que independentment de la dificultat d'un problema (és a dir de quants recursos d'espai i temps necessita), sempre hi haurà problemes més difícils. Això ho determina en el cas dels costos en temps el teorema de la jerarquia temporal. D'aquest es deriva també el teorema similar respecte l'espai.

Classes de complexitat

Els problemes de decisió es classifiquen en conjunts de complexitat anomenats classes de complexitat.

La classe de complexitat P és el conjunt de problemes de decisió que poden ser resolts en una màquina determinista en temps polinòmic, el que correspon intuïtivament als problemes que poden ser resolts fins i tot en el pitjor dels seus casos.

La classe de complexitat NP és el conjunt dels problemes de decisió que poden ser resolts per una màquina no determinista en un temps polinòmic. Aquesta classe conté molts problemes que es volen resoldre a la pràctica, incloent-hi el Problema de satisfacibilitat booleana, el problema del camí de Hamilton i el problema de la cobertura de vèrtexs. Tots els problemes d'aquesta classe tenen la propietat que la seva solució pot ser verificada efectivament.

La pregunta P=NP

Vegeu P versus NP

Intractabilitat

Els problemes que poden ser resolts en teoria, però no a la pràctica, s'anomenen intractables. Què es pot i què no a la pràctica és un tema debatible, però en general només els problemes que tenen solucions en temps polinòmics són solubles per més que uns quants valors. Problemes que se saben intractables inclouen els d'EXPTIME-complet. Si NP no és igual a P, llavors tots els problemes de NP-Complet són també intractables.

Per a veure per què les solucions de temps exponencial no són usables en la pràctica, es pot considerar un problema que requereix operacions 2ⁿ per a solucionar-se (n és la mida de la font d'informació). Per a una font d'informació relativament petita n = 100, i assumint que una computadora per fer unes 10¹⁰ (10 giga) operacions per segon, una solució necessitaria prop de 4*10¹² anys per a completar-se, molt més temps que l'edat de l'univers.

Investigadors en l'àrea

• Manindra Agrawal
• Sanjeev Arora
• Laszlo Babai
• Manuel Blum, que va desenvolupar la seva pròpia teoria de complexitat axiomàtica basant-se en els axiomes de Blum
• Allan Borodin
• Stephen Cook
• Lance Fortnow
• Juris Hartmanis
• Russell Impagliazzo
• Richard Karp
• Marek Karpinski
• Leonid Levin
• Richard Lipton
• Noam Nisan
• Christos H. Papadimitriou
• Alexander Razborov
• Walter Savitch
• Michael Sipser
• Richard Stearns
• Madhu Sudan
• Leslie Valiant
• Umesh Vazirani
• Avi Wigderson
• Andrew Yao
• Eugene Yarovoi

Bibliografia

• Harel,D., Algorithmics: The spirit of computing, Addison-Wesley, 1988.

Vegeu també

• P versus NP.
• Nombre de Shannon.
• Sistema formal.
• Jerarquia aritmètica.