Questo libro di testo per principianti descrive sia i risultati recenti che i risultati classici della teoria della complessità computazionale. Non richiedendo essenzialmente alcuna preparazione a parte la maturità matematica, il libro può essere utilizzato come riferimento per lo studio autonomo per chiunque sia interessato alla complessità, inclusi fisici, matematici e altri scienziati, nonché come libro di testo per una varietà di corsi e seminari. Sono inclusi più di 300 esercizi con un set di suggerimenti selezionato. Il libro inizia con un'ampia introduzione al campo e procede fino ai risultati avanzati. I contenuti includono: definizione delle macchine di Turing e classi di complessità di base di tempo e spazio, algoritmi probabilistici, dimostrazioni interattive, crittografia, calcolo quantistico, limiti inferiori per modelli computazionali concreti (alberi decisionali, complessità della comunicazione, profondità costante, circuiti algebrici e monotoni, complessità della dimostrazione), complessità nel caso medio e amplificazione della durezza, derandomizzazione e costruzioni pseudocasuali e teorema PCP.
caricamento...
