Complexitat computacional

De Viquip??dia

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 que 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??mica. 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.

Taula de continguts 1 Presentaci?? 2 Exemples 3 Problemes de decisi?? 4 Classes de complexitat 5 La pregunta P=NP 6 Intractabilitat 7 Investigadors en l'??rea 8 Vegeu tamb??

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

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

[edita] 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 trobar el factor m??s petit d'n, llavors es pot dividir aquest factor i es repeteix el proc??s fins 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.

[edita] 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 incl??s 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.

[edita] La pregunta P=NP

Vegeu P_versus_NP

[edita] 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 veure per que les solucions de temps exponencial no s??n usables a 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.

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

[edita] Vegeu tamb??

• P versus NP
• Llista de classes de complexitat
• Sistema formal
• Jerarquia aritm??tica

Plantilla:Classes de complexitat