Paddingtechnik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

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.