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. Neben den klassischen Komplexittsmaen Zeitaufwand und Speicherplatzbedarf werden eine Reihe weiterer Mae zur Strukturierung eingesetzt. Algorithmische Probleme werden diesbezglich klassifiziert und in Beziehung zueinander gesetzt. Die Suche nach effizienten Lsungsstrategien wird komplementiert durch den (im allgemeinen sehr schwierigen) Nachweis unterer Schranken fr den Lsungsaufwand. Komplexittstheoretische Resultate haben auch unmittelbare Bedeutung fr die Praxis erlangt, beispielsweise Ergebnisse aus dem Bereich der NP-Vollstndigkeit fr die Lsbarkeit von kombinatorischen Optimierungsproblemen sowie die Sicherheit von Cryptosystemen. Komplexittstheoretische Untersuchungen verwenden sehr wesentlich Methoden aus der Diskreten Mathematik, andererseits sind dabei auch eine Reihe neuartiger mathematischer Fragestellungen aufgeworfen worden.

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. Neben den klassischen Komplexitätsma en Zeitaufwand und Speicherplatzbedarf werden eine Reihe weiterer Ma e zur Strukturierung eingesetzt. Algorithmische Probleme werden diesbezüglich klassifiziert und in Beziehung zueinander gesetzt. Die Suche nach effizienten Lösungsstrategien wird komplementiert durch den (im allgemeinen sehr schwierigen) Nachweis unterer Schranken für den Lösungsaufwand.