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

Sei $L\in \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}$ und $N$ eine passende nichtdeterministische Turingmaschine mit Laufzeit $𝒪(2^{n^c})$ für ein festes $c$ abhängig von $L$. Konstruiere nun eine neue Sprache $L^{\prime }$, indem an jedes Wort eine bestimmte Zahl eines neuen Symbols (hier: $1$) angefügt wird:

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

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^{\prime }\in \mathrm{N}\mathrm{P}$, wie im Folgenden ausgeführt. Anschließend wird aus der Annahme $\mathrm{P}=\mathrm{N}\mathrm{P}$ abgeleitet, dass $L\in \mathrm{E}\mathrm{X}\mathrm{P}$.

$L^{\prime }$ kann für die Eingabe $x^{\prime }$ wie folgt in nichtdeterministisch polynomieller Zeit entschieden werden: Überprüfe, ob $x^{\prime }$ von der Form $x^{\prime }=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 $𝒪(2^{{|x|}^c})$, was polynomiell in der Größe von $x^{\prime }$ ist. Daher ist $L^{\prime }\in \mathrm{N}\mathrm{P}$.

Mit der Annahme $\mathrm{P}=\mathrm{N}\mathrm{P}$ gibt es eine deterministische Maschine $D$, die $L^{\prime }$ 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.