Unterabschnitte
Eine Sprache

ist genau dann

, wenn gilt:
Man kann mit Hilfe eines Backtrackingalgorithmus
25 die NTM für SAT simulieren. Die Simulation belegt nur polynomiellen Platz, nämlich soviel Platz wie die Länge der Formel
26:

.
(Dieser Beweis ist ähnlich dem von
)
In-Place-Acceptance bedeutet, daß die Turingmaschine
- in
Platz
- akzeptiert oder verwirft.
Wir benutzen eine universelle Turingmaschine

, die mitzählt, wieviel Bandzellen

benutzt:
Wir benutzen eine Tiefensuche, um den Berechnungsbaum von der Turingmaschine, welche in NP liegt zu durchgehen.
Die Rekursionstiefe ist durch ein Polynom

beschränkt (Definition von

). Bei einem PTIME-Algorithmus darf der Berechnungsbaum höchstens polynomielle Tiefe haben, um die Rekursion zu speichern. Das ist hier erfüllt.
Die Turingmaschine in

ist im Platz durch ein Polynom

beschränkt. Er ergibt sich für die Gesamtanzahl der Konfigurationen
27 der Turingmaschine:
Wir können eine Konstante

finden, so dass gilt:

exponentiell beschränkt
Haben wir keinen Beweis (glücklicherweise) gemacht
Wir haben nur gesagt, daß nach diesem Satz gilt:
Fußnoten
- ... Backtrackingalgorithmus25
- Tiefensuche
- ... Formel26
- sorry, doch keine Fussnote.
- ... Konfigurationen27
- Also Möglichkeiten, wie die Zeichen auf dem Band stehen können, Möglichkeiten wie der Zeiger stehen kann und Möglichkeiten in welchem Zustand sich die Turingmaschine momentan befindet.