Introduzione alla Complessita Computazionale

Il libro introduce in modo semplice ma rigoroso i principi del processo di 'calcolare tramite algoritmi', descrivendo i principali aspetti della teoria della calcolabilità per poi passare ad una trattazione esauriente degli aspetti fondamentali della complessità di calcolo. Un ruolo fondamentale è svolto dal concetto di riduzione, sviluppato sia nell'ambito della calcolabilità sia nell'ambito della complessità. A partire da questo vengono introdotte e analizzate le principali classi di problemi computazionali. Il testo contiene esempi ed esercizi che aiutano a chiarire i concetti introdotti e consentono al lettore di impadronirsi delle tecniche descritte. Il volume è rivolto pricipalmente a studenti e laureandi delle facoltà di matematica, ingegneria ed informatica.