Komplexitätstheorie Band I: Grundlagen
Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus
K. Rüdiger Reischuk
Die Komplexitätstheorie untersucht den algorithmischen Aufwand zur Lösung von Problemen mit Hilfe einer Maschine. Dabei werden Rechnermodelle wie Turing-Maschinen oder Registermaschinen verwendet, um von speziellen Architektur- und Implementationsdetails unabhängige Ergebnisse zu gewinnen.