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[Bearbeiten | Quelltext bearbeiten]

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.