EITC/IS/CCTF Fonaments de la teoria de la complexitat computacional

Com que la quantitat de recursos necessaris per executar un algorisme varia amb la mida de l'entrada, la complexitat sol expressar-se com una funció f(n), on n és la mida de l'entrada i f(n) és la complexitat del pitjor cas ( la quantitat màxima de recursos necessaris per a totes les entrades de mida n) o la complexitat mitjana del cas (la mitjana de la quantitat de recursos sobre totes les entrades de mida n). El nombre d'operacions elementals necessàries en una entrada de mida n s'indica habitualment com a complexitat temporal, on es creu que les operacions elementals triguen una quantitat de temps constant en un ordinador particular i canvien només per un factor constant quan s'executen en una màquina diferent. La quantitat de memòria requerida per un algorisme en una entrada de mida n es coneix com a complexitat espacial.

El temps és el recurs més considerat. Quan el terme "complexitat" s'utilitza sense qualificador, normalment es refereix a la complexitat del temps.

Les unitats de temps tradicionals (segons, minuts, etc.) no s'utilitzen en la teoria de la complexitat, ja que depenen massa de l'ordinador escollit i de l'avenç de la tecnologia. Per exemple, un ordinador actual pot executar un algorisme substancialment més ràpid que un ordinador de la dècada de 1960, però, això es deu als avenços tecnològics en el maquinari informàtic més que a una qualitat inherent de l'algorisme. L'objectiu de la teoria de la complexitat és quantificar les necessitats de temps inherents als algorismes, o les limitacions de temps fonamentals que un algorisme imposaria a qualsevol ordinador. Això s'aconsegueix comptant quantes operacions bàsiques es realitzen durant el càlcul. Aquests procediments es coneixen habitualment com a passos perquè es considera que triguen un temps constant en una màquina determinada (és a dir, no es veuen afectats per la quantitat d'entrada).

Un altre recurs important és la quantitat de memòria de l'ordinador necessària per realitzar algorismes.

Un altre recurs utilitzat sovint és la quantitat d'operacions aritmètiques. En aquest escenari, s'utilitza el terme "complexitat aritmètica". La complexitat temporal és generalment el producte de la complexitat aritmètica per un factor constant si es coneix una restricció superior a la mida de la representació binària dels nombres que es produeixen durant un càlcul.

La mida dels nombres enters utilitzats durant un càlcul no està limitada per a molts mètodes, i no és realista suposar que les operacions aritmètiques requereixen una quantitat de temps fixa. Com a resultat, la complexitat del temps, també coneguda com a complexitat de bits, pot ser significativament superior a la complexitat aritmètica. La dificultat aritmètica de calcular el determinant d'una matriu entera nn, per exemple, és O(n^3) per a tècniques estàndard (eliminació gaussiana). Com que la mida dels coeficients es pot expandir exponencialment durant el càlcul, la complexitat de bits dels mateixos mètodes és exponencial en n. Si aquestes tècniques s'utilitzen conjuntament amb l'aritmètica multimodular, la complexitat de bits es pot reduir a O(n^4).

La complexitat de bits, en termes formals, es refereix al nombre d'operacions sobre bits necessàries per executar un algorisme. Iguala la complexitat temporal fins a un factor constant en la majoria de paradigmes de computació. El nombre d'operacions sobre paraules màquina requerides pels ordinadors és proporcional a la complexitat del bit. Per als models realistes de càlcul, la complexitat del temps i la complexitat dels bits són, per tant, idèntiques.

El recurs que sovint es considera en l'ordenació i la cerca és la quantitat de comparacions d'entrades. Si les dades estan ben ordenades, aquest és un bon indicador de la complexitat del temps.

En totes les entrades potencials, comptar el nombre de passos en un algorisme és impossible. Com que la complexitat d'una entrada augmenta amb la seva mida, normalment es representa en funció de la mida de l'entrada n (en bits), i per tant la complexitat és una funció de n. Tanmateix, per a les entrades de la mateixa mida, la complexitat d'un algorisme pot variar substancialment. Com a resultat, s'utilitzen rutinàriament una varietat de funcions de complexitat.

La complexitat del pitjor cas és la suma de tota la complexitat per a totes les entrades de mida n, mentre que la complexitat del cas mitjà és la suma de tota la complexitat per a totes les entrades de mida n (això té sentit, ja que el nombre d'entrades possibles d'una mida donada és finit). Quan s'utilitza el terme "complexitat" sense definir-lo més, es té en compte la complexitat temporal del pitjor dels casos.

La complexitat del pitjor dels casos i la mitjana dels casos són notòriament difícils de calcular correctament. A més, aquests valors exactes tenen poca aplicació pràctica perquè qualsevol canvi de paradigma de màquina o de càlcul variaria lleugerament la complexitat. A més, l'ús de recursos no és important per a valors petits de n, per tant la facilitat d'implementació sovint és més atractiva que la baixa complexitat per a n petit.

Per aquests motius, es presta més atenció al comportament de la complexitat per a n alt, és a dir, el seu comportament asimptòtic quan n s'acosta a l'infinit. Com a resultat, la notació O gran s'utilitza habitualment per indicar complexitat.

Models computacionals

L'elecció d'un model de càlcul, que consisteix a especificar les operacions essencials que es realitzen en una unitat de temps, és important per determinar la complexitat. De vegades es coneix com una màquina de Turing multicinta quan el paradigma de càlcul no es descriu específicament.

Un model determinista de càlcul és aquell en què els estats posteriors de la màquina i les operacions a realitzar estan totalment definits per l'estat anterior. Les funcions recursives, el càlcul lambda i les màquines de Turing van ser els primers models deterministes. Les màquines d'accés aleatori (també conegudes com a màquines RAM) són un paradigma popular per simular ordinadors del món real.

Quan el model de càlcul no està definit, normalment s'assumeix una màquina de Turing multicinta. A les màquines Turing multicinta, la complexitat del temps és la mateixa que a les màquines RAM per a la majoria d'algoritmes, tot i que pot ser necessària una atenció considerable a com s'emmagatzemen les dades a la memòria per aconseguir aquesta equivalència.

Es poden fer diverses opcions en alguns passos del càlcul en un model de computació no determinista, com ara les màquines de Turing no deterministes. En la teoria de la complexitat, es consideren totes les opcions factibles al mateix temps, i la complexitat temporal no determinista és la quantitat de temps necessària quan sempre es prenen les millors eleccions. Per dir-ho d'una altra manera, el càlcul es fa simultàniament en tants processadors (idèntics) com siguin necessaris, i el temps de càlcul no determinista és el temps que triga el primer processador a completar el càlcul. Aquest paral·lelisme es pot utilitzar en la informàtica quàntica mitjançant l'ús d'estats entrellaçats superposats quan s'executen algorismes quàntics especialitzats, com ara la factorització de Shor de petits enters, per exemple.

Fins i tot si aquest model de càlcul no és practicable actualment, té un significat teòric, particularment en relació amb el problema P = NP, que pregunta si les classes de complexitat produïdes mitjançant l'ús de "temps polinomial" i "temps polinomi no determinista" són com a mínim superiors. els límits són els mateixos. En un ordinador determinista, simular un algorisme NP requereix "temps exponencial". Si una tasca es pot resoldre en temps polinomial en un sistema no determinista, pertany a la classe de dificultat NP. Si un problema està en NP i no és més fàcil que qualsevol altre problema NP, es diu que és NP-complet. El problema de la motxilla, el problema del venedor ambulant i el problema de satisfacció booleà són tots problemes combinatoris NP-complets. L'algorisme més conegut té una complexitat exponencial per a tots aquests problemes. Si algun d'aquests problemes es pogués resoldre en temps polinomial en una màquina determinista, llavors tots els problemes NP es podrien resoldre també en temps polinomial i s'establirien P = NP. A partir del 2017, s'assumeix àmpliament que P NP, la qual cosa implica que les pitjors situacions dels problemes de NP són fonamentalment difícils de resoldre, és a dir, triguen molt més que qualsevol període de temps factible (dècades) donades les longituds d'entrada interessants.

Informàtica paral·lela i distribuïda

La informàtica paral·lela i distribuïda implica dividir el processament entre diversos processadors que funcionen tots alhora. La distinció fonamental entre els diferents models és el mètode d'enviament de dades entre processadors. La transmissió de dades entre processadors sol ser molt ràpida en la informàtica paral·lela, mentre que la transferència de dades entre processadors en la informàtica distribuïda es fa a través d'una xarxa i, per tant, és substancialment més lenta.

Un càlcul amb N processadors pren almenys el quocient per N del temps que triga a un sol processador. En realitat, com que algunes subtasques no es poden paral·lelitzar i alguns processadors poden haver d'esperar un resultat d'un altre processador, aquest límit teòricament ideal mai s'aconseguirà.

El problema clau de la complexitat és, doncs, desenvolupar algorismes perquè el producte del temps de càlcul pel nombre de processadors sigui el més proper possible al temps necessari per realitzar el mateix càlcul en un sol processador.

Càlcul quàntic

Un ordinador quàntic és un ordinador amb un model de càlcul basat en la mecànica quàntica. La tesi Church-Turing és vàlida per als ordinadors quàntics, la qual cosa implica que qualsevol problema que pugui resoldre un ordinador quàntic també es pot resoldre amb una màquina de Turing. Tanmateix, algunes tasques es podrien resoldre teòricament utilitzant un ordinador quàntic en lloc d'un ordinador clàssic amb una complexitat temporal significativament menor. De moment, això és estrictament teòric, ja que ningú sap com desenvolupar un ordinador quàntic pràctic.

La teoria de la complexitat quàntica es va crear per investigar els diferents tipus de problemes que es poden resoldre amb les computadores quàntiques. S'utilitza en la criptografia postquàntica, que és el procés de creació de protocols criptogràfics resistents als atacs informàtics quàntics.

Complexitat del problema (límits inferiors)

L'ínfim de les complexitats dels algorismes que poden resoldre el problema, incloses les tècniques no descobertes, és la complexitat del problema. Com a resultat, la complexitat d'un problema és igual a la complexitat de qualsevol algorisme que el resolgui.

Com a resultat, qualsevol complexitat donada en notació O gran representa una complexitat tant de l'algorisme com del problema que l'acompanya.

D'altra banda, sovint és difícil obtenir límits inferiors no trivials sobre la complexitat del problema, i hi ha poques estratègies per fer-ho.

Per resoldre la majoria de problemes, s'han de llegir totes les dades d'entrada, la qual cosa triga un temps proporcional a la magnitud de les dades. Com a resultat, aquests problemes tenen almenys una complexitat lineal o, en notació omega gran, una complexitat de Ω(n).

Alguns problemes, com els de l'àlgebra informàtica i la geometria algebraica computacional, tenen solucions molt grans. Com que la sortida s'ha d'escriure, la complexitat està limitada per la mida màxima de la sortida.

El nombre de comparacions necessàries per a un algorisme d'ordenació té un límit inferior no lineal de Ω(nlogn). Com a resultat, els millors algorismes d'ordenació són els més eficients ja que la seva complexitat és O(nlogn). El fet que hi hagi n! maneres d'organitzar n coses condueixen a aquest límit inferior. Perquè cada comparació divideix aquesta col·lecció de n! ordres en dues peces, el nombre de N comparacions necessàries per distingir totes les ordres ha de ser 2N > n!, la qual cosa implica O(nlogn) per la fórmula de Stirling.

Reduir un problema a un altre és una estratègia comuna per obtenir restriccions de complexitat reduïdes.

Desenvolupament d'algoritmes

L'avaluació de la complexitat d'un algorisme és un element important del procés de disseny, ja que proporciona informació útil sobre el rendiment que es pot esperar.

És un malentès freqüent que, com a resultat de la llei de Moore, que prediu el creixement exponencial de la potència de l'ordinador modern, l'avaluació de la complexitat dels algorismes serà menys rellevant. Això és incorrecte perquè l'augment de potència permet processar quantitats massives de dades (big data). Per exemple, qualsevol algorisme hauria de funcionar bé en menys d'un segon en ordenar alfabèticament una llista d'uns quants centenars d'entrades, com ara la bibliografia d'un llibre. D'altra banda, per a un milió d'entrades (per exemple, els números de telèfon d'una gran ciutat), els algorismes bàsics que requereixen comparacions O(n2) haurien de realitzar un bilió de comparacions, que trigarien tres hores a una velocitat de 10. milions de comparacions per segon. D'altra banda, l'ordenació ràpida i l'ordenació per fusió només requereixen comparacions de nlogn (com a complexitat mitjana del cas per al primer, com a complexitat del pitjor cas per al segon). Això produeix al voltant de 30,000,000 de comparacions per a n = 1,000,000, la qual cosa trigaria només 3 segons a 10 milions de comparacions per segon.

Com a resultat, l'avaluació de la complexitat pot permetre l'eliminació de molts algorismes ineficients abans de la implementació. Això també es pot utilitzar per afinar algorismes complexos sense haver de provar totes les variants possibles. L'estudi de la complexitat permet centrar l'esforç per augmentar l'eficiència d'una implementació mitjançant la determinació dels passos més costosos d'un algorisme complex.