Paddingtechnik

Die Paddingtechnik i​st ein Verfahren d​er Komplexitätstheorie, u​m nachzuweisen, d​ass die Gleichheit bestimmter Komplexitätsklassen d​ie Gleichheit größerer n​ach sich zieht.

Beispiel

Der Beweis, dass aus ${\displaystyle \mathrm {P} =\mathrm {NP} }$ auch ${\displaystyle \mathrm {EXP} =\mathrm {NEXP} }$ folgt, verwendet Padding. Da ${\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} }$ nach Definition gilt, genügt es ${\displaystyle \mathrm {EXP} \supseteq \mathrm {NEXP} }$ zu zeigen. (Wegen Kontraposition zeigt dies auch, dass aus ${\displaystyle \mathrm {EXP} \neq \mathrm {NEXP} }$ auch ${\displaystyle \mathrm {P} \neq \mathrm {NP} }$ folgt.)

Sei ${\displaystyle L\in \mathrm {NEXP} }$ und ${\displaystyle N}$ eine passende nichtdeterministische Turingmaschine mit Laufzeit ${\displaystyle {\mathcal {O}}(2^{n^{c}})}$ für ein festes ${\displaystyle c}$ abhängig von ${\displaystyle L}$. Konstruiere nun eine neue Sprache ${\displaystyle L'}$, indem an jedes Wort eine bestimmte Zahl an 1en angefügt werden:

${\displaystyle L':=\left\{x\ 1^{2^{|x|^{c}}}\mid x\in L\right\}}$

wobei ${\displaystyle 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 ${\displaystyle L'\in \mathrm {NP} }$, wie im Folgenden ausgeführt. Anschließend wird aus der Annahme ${\displaystyle \mathrm {P} =\mathrm {NP} }$ abgeleitet, dass ${\displaystyle L\in \mathrm {EXP} }$.

${\displaystyle L'}$ kann für die Eingabe ${\displaystyle x'}$ wie folgt in nichtdeterministisch polynomieller Zeit entschieden werden: Überprüfe, ob ${\displaystyle x'}$ von der Form ${\displaystyle x'=x\ 1^{2^{{|x|}^{c}}}}$ ist, und verwirf, falls dies nicht der Fall ist. Andernfalls simuliere die nichtdeterministische Turingmaschine ${\displaystyle N}$ mit Eingabe ${\displaystyle x}$. Die Simulation benötigt nichtdeterministisch die Zeit ${\displaystyle {\mathcal {O}}(2^{{|x|}^{c}})}$, was polynomiell in der Größe von ${\displaystyle x'}$ ist. Daher ist ${\displaystyle L'\in \mathrm {NP} }$.

Mit der Annahme ${\displaystyle \mathrm {P} =\mathrm {NP} }$ gibt es eine deterministische Maschine ${\displaystyle D}$, die ${\displaystyle L'}$ in Polynomialzeit entscheidet. Die Sprache ${\displaystyle L}$ ist dann in Exponentialzeit entscheidbar, indem für eine Eingabe ${\displaystyle x}$ die Maschine ${\displaystyle D}$ auf der Eingabe ${\displaystyle x\ 1^{2^{{|x|}^{c}}}}$ simuliert wird. Das benötigt nur exponentiell viel Zeit in Abhängigkeit von der Eingabegröße.

Dieses Argument w​ird gelegentlich a​uch für Platzkomplexität, alternierende Klassen u​nd 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.