Niniejsza książka jest uważana w świecie za najlepszy podręcznik teorii złożoności obliczeniowej. Autor wprowadza Czytelnika w trudny świat algorytmów i barier obliczalności. Omawia najważniejsze tematy dotyczące maszyn Turinga, klas złożoności, redukcji, zupełności, obliczeń równoległych i ich związku z obliczeniami w małej pamięci.