Bisher haben wir Probleme mit Turingmaschinen (bzw., was ja wegen der Church-Turing-These das gleiche ist, mit einem Algorithmus) gelöst. Dabei ging es bei der Entscheidbarkeit bzw. Unentscheidbarkeit eines Problems zunächst darum, ob ein Problem prinzipiell gelöst werden kann oder nicht. Für die Praxis reicht diese Unterscheidung aber in den allermeisten Fällen nicht. Wenn ein Problem zwar lösbar ist, die Zeit zur Lösung des Problems aber inakzeptabel ist, dann ist das Problem praktisch nicht lösbar. Hat man bspw. einen Algorithmus für ein Graphenproblem, der \(2^n\) viele Schritte zur Lösung des Problems braucht, wobei \(n\) die Anzahl der Knoten des Graphen ist. Dann ist dies für kleine Werte von \(n\) wie \(n = 20\) oder \(n = 30\) vielleicht noch akzeptabel, für z.B. \(n = 100\) wird die Berechnung einer Lösung aber nicht mehr möglich sein, weil diese schlicht zu lange dauert.

Entsprechend verhält es sich bei dem Erfüllbarkeitsproblem der Aussagenlogik, also bei dem Problem gegeben eine aussagenlogische Formel, ist diese erfüllbar oder nicht? Hat eine Formel \(n\) verschiedene Aussagensymbole, so hat die Wahrheitstafel, aus der man die Lösung ablesen kann, \(2^n\) viele Zeilen. Die Berechnung all dieser Zeilen dauert für größere \(n\) schlicht zu lange.

In der Komplexitätstheorie geht es nun zunächst darum, formal ein Maß für die Zeitkomplexität und die Platzkomplexität einer Berechnung zu definieren. Im Anschluss wird es dann darum gehen, wie man untere Schranken für ein Problem definieren kann, d.h. wie man ausdrücken kann, dass ein Problem (wie z.B. das Erfüllbarkeitsproblem der Aussagenlogik) auf keinen Fall schneller als eine bestimmte untere Schranke gelöst werden kann. Wir werden sehen, dass eine solche Schranke nicht einfach zu bestimmen ist. Tatsächlich stellt dies die Informatiker vor sehr große Probleme und wir können bisher nur Aussagen treffen, dass es mit einer hohen Wahrscheinlichkeit wohl keine Möglichkeit gibt, ein Problem schnell zu lösen. Aber Techniken, um dies mit Sicherheit zeigen zu können, sind im Moment außerhalb unserer Möglichkeiten. Diese Überlegungen werden in das Themengebiet \(P\), \(NP\) und \(NP\)-Vollständigkeit münden.