Paddingtechnik

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

Beispiel

Der Beweis, dass aus P=NP auch EXP=NEXP folgt, verwendet Padding. Da EXP⊆NEXP nach Definition gilt, genügt es EXP⊇NEXP zu zeigen. (Wegen Kontraposition zeigt dies auch, dass aus EXP≠NEXP auch P≠NP folgt.)

Sei L∈NEXP und N eine passende nichtdeterministische Turingmaschine mit Laufzeit 𝒪(2nc) für ein festes c abhängig von L. Konstruiere nun eine neue Sprache L′, indem an jedes Wort eine bestimmte Zahl eines neuen Symbols (hier: 1) angefügt wird:

L′:={x 12|x|c|x∈L}

wobei 1∉L. 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 L′∈NP, wie im Folgenden ausgeführt. Anschließend wird aus der Annahme P=NP abgeleitet, dass L∈EXP.

L′ kann für die Eingabe x′ wie folgt in nichtdeterministisch polynomieller Zeit entschieden werden: Überprüfe, ob x′ von der Form x′=x 12|x|c ist, und verwirf, falls dies nicht der Fall ist. Andernfalls simuliere die nichtdeterministische Turingmaschine N mit Eingabe x. Die Simulation benötigt nichtdeterministisch die Zeit 𝒪(2|x|c), was polynomiell in der Größe von x′ ist. Daher ist L′∈NP.

Mit der Annahme P=NP gibt es eine deterministische Maschine D, die L′ in Polynomialzeit entscheidet. Die Sprache L ist dann in Exponentialzeit entscheidbar, indem für eine Eingabe x die Maschine D auf der Eingabe x 12|x|c 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