Denne graduate læreboken gir en omfattende oversikt over både nylige prestasjoner og klassiske resultater innenfor teoretisk beregningskompleksitet. Boken krever i hovedsak ingen forkunnskaper utover matematisk modenhet, noe som gjør den til et nyttig oppslagsverk for egenstudier for alle som er interessert i kompleksitet – det inkluderer fysikere, matematikere og andre forskere. Den kan også benyttes som lærebok for en rekke kurs og seminarer. Med mer enn 300 oppgaver, inkludert et utvalg hints, er boken designet for å gi leserne en praktisk tilnærming til emnet. Innholdet åpner med en grundig introduksjon til området og beveger seg deretter mot mer avanserte resultater. Temaene som dekkes inkluderer: definisjon av Turing-maskiner og grunnleggende tid- og plasskompleksitetsklasser, probabilistiske algoritmer, interaktive bevis, kryptografi, kvanteberegning, lavere grenser for konkrete beregningsmodeller (beslutningstrær, kommunikasjonskompleksitet, konstant dybde, algebraiske og monotone kretser, beviskompleksitet), gjennomsnittlig kompleksitet og hardhetsforsterkning, derandomisering og pseudorandom-kontruksjoner, samt flere andre sentrale emner innenfor feltet.
