Strettamente campi strettamente correlati nella scienza informatica teorica sono l' analisi di algoritmi e la teoria computabilità. Una distinzione chiave tra l' analisi degli algoritmi e la teoria della complessità computazionale è che la prima è dedicata all' analisi della quantità di risorse necessarie ad un particolare algoritmo per risolvere un problema, mentre la seconda pone una domanda più generale su tutti i possibili algoritmi che potrebbero essere usati per risolvere lo stesso problema. Più precisamente, cerca di classificare i problemi che possono o non possono essere risolti con risorse opportunamente limitate. A sua volta, imporre restrizioni alle risorse disponibili è ciò che distingue la complessità computazionale dalla teoria della computabilità: quest' ultima teoria chiede che tipo di problemi possono, in linea di principio, essere risolti algoritmicamente.
Quale campo di computer science analizza tutti i possibili algoritmi in aggregato per determinare le risorse necessarie per risolvere un dato problema?
teoria della complessità computazionale teoria della complessità computazionale teoria della complessità computazionale