パディング引数

計算複雑性理論において、パディング議論は、いくつかの複雑性クラスが等しい場合、他のいくつかのより大きなクラスも等しいこと を条件付きで証明するためのツールです。

P  =  NP がEXP  =  NEXP を意味するという証明には 「パディング」が使用されます。

${\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} }$定義により、 なので、 を示せば十分です。 ${\displaystyle \mathrm {NEXP} \subseteq \mathrm {EXP} }$

L をNEXP の言語とします。LはNEXP なので、ある定数cに対して時間内にL を決定する非決定性チューリングマシン Mが存在します。 ${\displaystyle 2^{n^{c}}}$

${\displaystyle L'=\{x1^{2^{|x|^{c}}}\mid x\in L\},}$

ここで、「1」はLに出現しない記号です。まず、が NP に含まれることを示し、次に P = NP で与えられる決定論的多項式タイムマシンを使用して、Lが EXP に含まれることを示します。 ${\displaystyle L'}$

${\displaystyle L'}$は、次のように非決定性多項式時間で決定できます。入力 が与えられた場合、それが形式 であることを確認し、そうでない場合は拒否します。正しい形式である場合は、M ( x ) をシミュレートします。シミュレーションには非決定性時間がかかり、入力のサイズ の多項式時間になります。したがって、は NP 単位です。P = NP という仮定により、多項式時間で決定する決定性マシンDMも存在します。次に、次のようにL を決定性指数時間で決定できます。入力 が与えられた場合、 をシミュレートします。これは、入力のサイズ の指数時間のみかかります。 ${\displaystyle x'}$${\displaystyle x'=x1^{2^{|x|^{c}}}}$${\displaystyle 2^{|x|^{c}}}$${\displaystyle x'}$${\displaystyle L'}$${\displaystyle L'}$${\displaystyle x}$${\displaystyle DM(x1^{2^{|x|^{c}}})}$${\displaystyle x}$

は言語Lの「パディング」と呼ばれます。このタイプの議論は、空間計算量クラス、交代クラス、および境界付き交代クラス にも使用されることがあります。${\displaystyle 1^{d}}$

• パディング可能な言語

• アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性：現代的アプローチ、ケンブリッジ、p. 57、ISBN 978-0-521-42426-4