Die Paddingtechnik ist ein Verfahren der Komplexitätstheorie, um nachzuweisen, dass die Gleichheit bestimmter Komplexitätsklassen die Gleichheit größerer nach sich zieht.

Beispiel

Bearbeiten

Der Beweis, dass aus   auch   folgt, verwendet Padding. Da   nach Definition gilt, genügt es   zu zeigen. (Wegen Kontraposition zeigt dies auch, dass aus   auch   folgt.)

Sei   und   eine passende nichtdeterministische Turingmaschine mit Laufzeit   für ein festes   abhängig von  . Konstruiere nun eine neue Sprache  , indem an jedes Wort eine bestimmte Zahl eines neuen Symbols (hier:  ) angefügt wird:

 

wobei  . Durch dieses Padding wird die Länge der Wörter künstlich aufgebläht, ohne die Schwierigkeit des Entscheidungsproblems wesentlich zu erhöhen. Mit dieser Konstruktion ist  , wie im Folgenden ausgeführt. Anschließend wird aus der Annahme   abgeleitet, dass  .

  kann für die Eingabe   wie folgt in nichtdeterministisch polynomieller Zeit entschieden werden: Überprüfe, ob   von der Form   ist, und verwirf, falls dies nicht der Fall ist. Andernfalls simuliere die nichtdeterministische Turingmaschine   mit Eingabe  . Die Simulation benötigt nichtdeterministisch die Zeit  , was polynomiell in der Größe von   ist. Daher ist  .

Mit der Annahme   gibt es eine deterministische Maschine  , die   in Polynomialzeit entscheidet. Die Sprache   ist dann in Exponentialzeit entscheidbar, indem für eine Eingabe   die Maschine   auf der Eingabe   simuliert wird. Das benötigt nur exponentiell viel Zeit in Abhängigkeit von der Eingabegröße.

Dieses Argument wird gelegentlich auch für Platzkomplexität, alternierende Klassen und beschränkte alternierende Klassen gebraucht.

Siehe auch

Bearbeiten

Literatur

Bearbeiten