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 $\mathrm {P} =\mathrm {NP}$ auch $\mathrm {EXP} =\mathrm {NEXP}$ folgt, verwendet Padding. Da $\mathrm {EXP} \subseteq \mathrm {NEXP}$ nach Definition gilt, genügt es $\mathrm {EXP} \supseteq \mathrm {NEXP}$ zu zeigen. (Wegen Kontraposition zeigt dies auch, dass aus $\mathrm {EXP} \neq \mathrm {NEXP}$ auch $\mathrm {P} \neq \mathrm {NP}$ folgt.)

Sei $L\in \mathrm {NEXP}$ und $N$ eine passende nichtdeterministische Turingmaschine mit Laufzeit ${\mathcal {O}}(2^{n^{c}})$ 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':={\biggl \{}\,x\ 1^{2^{|x|^{c}}}\,{\bigg |}\,x\in L\,{\biggr \}}$

wobei $1\notin 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'\in \mathrm {NP}$, wie im Folgenden ausgeführt. Anschließend wird aus der Annahme $\mathrm {P} =\mathrm {NP}$ abgeleitet, dass $L\in \mathrm {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\ 1^{2^{{|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 ${\mathcal {O}}(2^{{|x|}^{c}})$, was polynomiell in der Größe von $x'$ ist. Daher ist $L'\in \mathrm {NP}$.

Mit der Annahme $\mathrm {P} =\mathrm {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\ 1^{2^{{|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

• P-NP-Problem
• EXP und NEXP

Literatur

• Sanjeev Arora, Boaz Barek (2009): Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge/ New York 2009, ISBN 978-0-521-42426-4, S. 57.