La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme.
Es considera que un problema és inherentment difícil si la seva solució requereix recursos importants, sigui quin sigui l'algorisme utilitzat. La teoria formalitza aquesta intuïció, introduint models matemàtics de càlcul per estudiar aquests problemes i quantificant-ne la complexitat computacional, és a dir, la quantitat de recursos necessaris per resoldre'ls, com el temps i la necessitat d'emmagatzematge. També s'utilitzen altres mesures de complexitat, com ara la quantitat de comunicació (utilitzada en complexitat de comunicació), el nombre de portes en un circuit (utilitzat en complexitat de circuits) i el nombre de processadors (utilitzat en informàtica paral·lela). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics del que els ordinadors poden i no poden fer. El problema P versus NP, un dels set problemes del Premi del Mil·lenni, està dedicat al camp de la complexitat computacional.
Camps estretament relacionats en la informàtica teòrica són l'anàlisi d'algorismes i la teoria de la computabilitat. La primera es dedica a analitzar la quantitat de recursos que necessita un algorisme en particular per resoldre un problema, mentre que la segona fa una pregunta més general sobre tots els possibles algorismes que es podrien utilitzar per resoldre el mateix problema. Més concretament, la teoria de la complexitat computacional intenta classificar problemes que es poden o no resoldre amb recursos restringits adequadament. Al seu torn, imposar restriccions als recursos disponibles és el que distingeix la complexitat computacional de la teoria de la computabilitat: aquesta darrera teoria es pregunta quin tipus de problemes es poden, en principi, resoldre algorítmicament.
Problemes computacionals miniatura| Un viatge de viatjant de comerç per 14 ciutats alemanyes
Instàncies problemàtiques Un problema computacional es pot veure com una col·lecció infinita d’instàncies juntament amb un conjunt (possiblement buit) de solucions per a cada instància. La cadena d'entrada per a un problema computacional s'anomena instància del problema i no s'ha de confondre amb el problema en si. En la teoria de la complexitat computacional, un problema es refereix a la qüestió abstracta que s'ha de resoldre. En canvi, una instància d'aquest problema és una enunciació força concreta, que pot servir com a entrada per a un problema de decisió. Per exemple, considerem el problema de les proves de primalitat. La instància és un nombre (per exemple, 15) i la solució és sí si el nombre és primer i no en cas contrari (en aquest cas, 15 no és primer i la resposta és no). Dit d'una altra manera, la instància és una entrada particular del problema, i la solució és la sortida corresponent a l'entrada donada.
Per destacar encara més la diferència entre un problema i una instància, considereu la següent instància de la versió de decisió del problema del viatjant de comerç: Hi ha una ruta de com a màxim 2000 quilòmetres que passi per les 14 ciutats més grans d'Alemanya? La resposta quantitativa a aquesta instància particular del problema és de poca utilitat per resoldre altres instàncies del problema, com ara demanar un viatge d'anada i tornada a través de 14 llocs a Milà, la longitud total dels quals és com a màxim de 10 km. Per aquesta raó, la teoria de la complexitat aborda problemes computacionals i no instàncies particulars de problemes.
Representació d'instàncies problemàtiques Quan es consideren problemes computacionals, una instància de problema és una cadena sobre un caràcter alfabètic. Normalment, l'alfabet es pren com l'alfabet binari (és a dir, el conjunt {0,1}), i per tant les cadenes són cadenes de bits. Igual que en un ordinador del món real, els objectes matemàtics que no siguin cadenes de bits s'han de codificar adequadament. Per exemple, els nombres enters es poden representar en notació binària, i els gràfics es poden codificar directament mitjançant les seves matrius d'adjacència o codificant les seves llistes d'adjacència en binari.
Tot i que algunes demostracions de teoremes de la teoria de la complexitat assumeixen regularment alguna elecció concreta de codificació d'entrada, s'intenta mantenir la discussió prou abstracta per ser independent de l'elecció precisa de codificació. Això es pot aconseguir assegurant-se que les diferents representacions es puguin transformar les unes en les altres de manera eficient.
Problemes de decisió com a llenguatges formals miniatura| Un problema de decisió només té dues sortides possibles, sí o no (o alternativament 1 o 0) en qualsevol entrada. Els problemes de decisió són un dels objectes centrals d'estudi de la teoria de la complexitat computacional. Un problema de decisió és un tipus de problema computacional on la resposta és sí o no (alternativament, 1 o 0). Un problema de decisió es pot veure com un llenguatge formal, on els membres del llenguatge són instàncies la sortida de les quals és sí, i els no membres són aquelles instàncies la sortida de les quals és no. L'objectiu és decidir, amb l'ajuda d'un algoritme, si una cadena d'entrada determinada és membre del llenguatge formal en qüestió. Si l'algoritme que resol aquest problema retorna la resposta sí, es diu que l'algoritme accepta la cadena d'entrada; en cas contrari, es diu que la rebutja.
Un exemple de problema de decisió és el següent. L'entrada és un gràfic arbitrari. El problema consisteix a decidir si el graf donat és connectat o no. El llenguatge formal associat amb aquest problema de decisió és, doncs, el conjunt de tots els grafs connectats; per obtenir una definició precisa d'aquest llenguatge, cal decidir com es codifiquen els grafs com a cadenes binàries.
Problemes de funció Un problema de funció és un problema computacional on s'espera una única sortida (d'una funció total) per a cada entrada, però la sortida pot ser més complexa que la d'un problema de decisió, és a dir, la sortida no és només sí o no. Exemples notables inclouen el problema del viatjant de comerç i el problema de la factorització entera.
Resulta temptador pensar que la noció de problemes de funcions és molt més rica que la noció de problemes de decisió. Tanmateix, això no és realment el cas, ja que els problemes de funcions es poden reformular com a problemes de decisió. Per exemple, la multiplicació de dos nombres enters es pot expressar com el conjunt de terns de manera que la relació sosté. Decidir si un triplet donat és membre d'aquest conjunt correspon a resoldre el problema de multiplicar dos nombres.
Mesurar la mida d'una instància Per mesurar la dificultat de resoldre un problema computacional, es pot voler veure quant de temps triga el millor algorisme a resoldre el problema. No obstant això, el temps d'execució pot, en general, dependre de la instància. En particular, les instàncies més grans requeriran més temps per resoldre-les. Així, el temps necessari per resoldre un problema (o l'espai requerit, o qualsevol mesura de complexitat) es calcula com a funció de la mida de la instància. La mida d'entrada es mesura normalment en bits. La teoria de la complexitat estudia com els algoritmes s'escalen a mesura que augmenta la mida de l'entrada. Per exemple, en el problema de trobar si un graf està connectat, quant més temps es triga a resoldre un problema per a un graf amb vèrtexs en comparació amb el temps que triga un gràfic amb vèrtexs.
Si la mida d'entrada és , el temps que es triga es pot expressar com una funció de . Com que el temps que es triga en diferents entrades de la mateixa mida pot ser diferent, la complexitat temporal del pitjor dels casos es defineix com el temps màxim que es triga a realitzar totes les entrades de mida . Si és un polinomi en , aleshores es diu que l'algoritme és un algorisme de temps polinòmic. La tesi de Cobham argumenta que un problema es pot resoldre amb una quantitat factible de recursos si i només si admet un algorisme de temps polinòmic.
Models de màquines i mesures de complexitat Màquina de Turing miniatura| Una il·lustració d'una màquina de Turing Una màquina de Turing és un model matemàtic d'una màquina de computació en general.Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edició, MIT Press and McGraw-Hill, (pàgina 1049). És un dispositiu teòric que manipula símbols continguts en una tira de cinta adhesiva. Les màquines de Turing no estan concebudes com una tecnologia informàtica pràctica, sinó com un model general d'una màquina informàtica, des d'un superordinador avançat fins a un matemàtic amb un llapis i paper. Es creu que si un problema es pot resoldre amb un algoritme, existeix una màquina de Turing que resol el problema. De fet, aquesta és l'afirmació de la tesi de Church-Turing. A més, se sap que tot allò que es pot calcular en altres models de computació que coneixem avui dia, com ara una màquina RAM, el Joc de la Vida de Conway, els autòmats cel·lulars, el càlcul lambda o qualsevol llenguatge de programació, es pot calcular en una màquina de Turing. Com que les màquines de Turing són fàcils d'analitzar matemàticament i es creu que són tan potents com qualsevol altre model de computació, la màquina de Turing és el model més utilitzat en la teoria de la complexitat.
Molts tipus de màquines de Turing s'utilitzen per definir classes de complexitat, com ara màquines de Turing deterministes, màquines de Turing probabilístiques, màquines de Turing no deterministes, màquines de Turing quàntiques, màquines de Turing simètriques i màquines de Turing alternes. En principi, tots són igualment poderosos, però quan els recursos (com el temps o l'espai) estan limitats, alguns poden ser més poderosos que d'altres.
Una màquina de Turing determinista és la màquina de Turing més bàsica, que utilitza un conjunt fix de regles per determinar les seves accions futures. Una màquina de Turing probabilística és una màquina de Turing determinista amb un subministrament addicional de bits aleatoris. La capacitat de prendre decisions probabilístiques sovint ajuda els algoritmes a resoldre problemes de manera més eficient. Els algoritmes que utilitzen bits aleatoris s'anomenen algoritmes aleatoris. Una màquina de Turing no determinista és una màquina de Turing determinista amb una característica afegida de no determinisme, que permet a una màquina de Turing tenir múltiples accions futures possibles a partir d'un estat donat. Una manera de veure el no determinisme és que la màquina de Turing es ramifica en molts camins computacionals possibles a cada pas, i si resol el problema en qualsevol d'aquestes branques, es diu que ha resolt el problema. Clarament, aquest model no pretén ser un model físicament realitzable, sinó una màquina abstracta teòricament interessant que dóna lloc a classes de complexitat particularment interessants. Per exemples, vegeu algorisme no determinista.
Altres models de màquina A la literatura s'han proposat molts models de màquines diferents de les màquines de Turing multicinta estàndard, per exemple, màquines d'accés aleatori. Potser sorprenentment, cadascun d'aquests models es pot convertir en un altre sense proporcionar cap potència computacional addicional. El consum de temps i memòria d'aquests models alternatius pot variar. El que tots aquests models tenen en comú és que les màquines funcionen deterministament.