K. Rüdiger Reischuk: Komplexitätstheorie – Band I: Grundlagen: Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. 2. Auflage. Teubner, Stuttgart/Leipzig 1999, ISBN 3-519-12275-8.
Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3. (International Edition)
Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. 1. Auflage. Springer, Berlin 2003, ISBN 3-540-00161-1.