La teoria della complessità computazionale è una disciplina relativamente recente che ha come obiettivo principale quello di formalizzare il concetto di complessità di un problema.
Questo volume ha un carattere introduttivo e si propone di presentare al lettore un quadro sistematico dei risultati più significativi ottenuti finora nel campo di questa nuova teoria.
L'approccio seguito consiste nel definire nei capitoli iniziali gli strumenti con i quali affrontare lo studio per poi passare ad esaminare in dettaglio le caratteristiche delle classi di complessità più importanti. Gli ultimi capitoli sono dedicati allo studio di classi di complessità probabilistiche ed a quello della complessità del calcolo parallelo.
Usato in ambito universitario, il testo permette di coprire le esigenze di più moduli didattici sia in corsi di informatica che nell'ambito di corsi interessati a vari aspetti della matematica che nell'ambito di corsi interessati a vari aspetti della matematica computazionale.
Un secondo tipo di lettori è costituito da quanti hanno già una buona preparazione informatica e desiderano approfondire gli sviluppi metodologici più significativi della teoria della complessità, sia per iniziare un'attività di ricerca in tale campo che per impadronirsi rapidamente di alcuni concetti o tecniche di dimostrazione per poi trasferirli in altri campi dell'informatica teorica.
Ogni capitolo è corredato di numerosi esempi e problemi che aiutano il lettore ad assimilare i nuovi concetti introdotti.