Komplexitätstheorie
Beschreibung
Seit der Defintion des Algorithmus untersucht man deren Komplexität, das heißt man stellt Laufzeituntersuchungen über alle möglichen Algorithmen an, die das spezifizierte Problem lösen.
Eines der größten Probleme der theoretischen Informatik, das P=NP Problem stammt aus dem Bereich der Komplexitätstheorie. Bei diesem Problem geht es grob gesprochen um die Frage, ob effiziente Verifizierbarkeit schon effiziente Konstruierbarkeit impliziert. Trotz vieler Bemühungen dieses Problem zu lösen gibt es bis heute noch keinen vernünftigen Ansatz, der in der Lage ist das Problem zu lösen.
Ein weiterer Zweig der Komplexitätstheorie ist die sogennante deskriptive Komplexitätstheorie oder endliche Modelltheorie. Diese versucht mittels formaler Logik Probleme zu beschreiben und anhand der Struktur dieser formalen Aussage die Komplexität des Problems zu berechnen.
Literaturempfehlungen
Descriptive Complexity,
Neil Immerman, 1999, Springer, ISBN 0-387-98600-6Structural Complexity I,
José Balcázar et al., 1988, Springer, ISBN 3-540-18622-0Structural Complexity II,
José Balcázar et al., 1988, Springer, ISBN 3-540-52079-1