パラメータ化された複雑性

FPT （固定パラメータ可解）とは、決定論的時間で決定可能な決定問題のクラスのことである。${\displaystyle f(k)\cdot {|x|}^{O(1)}}$ここで、fは計算可能な関数です。通常、この関数は、例えば、単一指数関数であると考えられています。$2^{O(k)}}$しかし、定義ではさらに速く増加する関数も許容される。これは、このクラスの初期の歴史の大部分にとって不可欠である。定義の重要な部分は、次の形式の関数を除外することである。${\displaystyle f(n,k)}$、 のような${\displaystyle k^{n}}$。

FPL （固定パラメータ線形）クラスは、時間内に解ける問題のクラスである。${\displaystyle f(k)\cdot |x|}$ある計算可能な関数fに対して。^{[ 2 ]}したがって、FPL は FPT のサブクラスである。例として、変数の数によってパラメータ化されたブール充足可能性問題がある。k個の変数を持つサイズmの与えられた式は、総当たりで時間でチェックできる。${\displaystyle O(2^{k}m)}$次数nのグラフにおけるサイズkの頂点被覆は、時間で見つけることができる。${\displaystyle O(2^{k}n)}$つまり、頂点被覆問題もFPLに含まれる。

FPTに含まれないと考えられる問題の一例として、色の数でパラメータ化されたグラフ彩色問題が挙げられます。3彩色問題はNP困難であることが知られており、 k彩色問題に対するアルゴリズムは時間で解けることが知られています。${\displaystyle f(k)n^{O(1)}}$のために${\displaystyle k=3}$入力のサイズに対して多項式時間で実行される。したがって、色の数でパラメータ化されたグラフ彩色が FPT に属する場合、P  =  NPとなる。

FPTにはいくつかの代替定義があります。たとえば、実行時間要件は次のように置き換えることができます。${\displaystyle f(k)+|x|^{O(1)}}$また、パラメータ化された問題は、いわゆるカーネルを持つ場合、FPT に属します。カーネル化とは、元のインスタンスを「ハードカーネル」と呼ばれる、元のインスタンスと同等でありながら、パラメータ内の関数によってサイズが制限される、場合によってははるかに小さなインスタンスに縮小する前処理技術です。

FPT はfpt-reductionsと呼ばれるパラメーター化された還元概念の下で閉じられています。パラメーター化された問題が 1 つあるとします。${\displaystyle L}$fpt 還元して${\displaystyle L'}$2つの関数が存在する場合${\displaystyle (x,k)\mapsto x',k\mapsto k'}$、したがって

• ${\displaystyle (x,k)\in L}$もし${\displaystyle (x',k')\in L'}$
• ${\displaystyle (x,k)\mapsto x'}$それ自体は固定パラメータ扱い可能である。
  • つまり、定数が存在する${\displaystyle c}$、そして関数${\displaystyle k\mapsto k''}$、したがって${\displaystyle (x,k)\mapsto x'}$時間で計算可能${\displaystyle \leq k''|x|^{c}}$

明らかに、FPTには多項式時間で計算可能な問題がすべて含まれている。さらに、効率的な多項式時間近似スキーム（EPTAS）が適用可能なNP内のすべての最適化問題も含まれている。

XPは、時間内に解決できるパラメータ化された問題のクラスです。${\displaystyle n^{f(k)}}$ある計算可能な関数fに対して。

これらの問題は、固定されたkの各「スライス」に対して多項式時間アルゴリズムが存在するという意味で、スライス単位多項式問題と呼ばれます。ただし、 kごとに指数が異なる可能性があります。これを、k の各値に対して異なる定数係数を許容するだけの FPT と比較してください。

XPは対角線法によってFPTを厳密に包含する。

para-NPは、非決定論的時間で決定可能な決定問題のクラスである。${\displaystyle f(k)\cdot |x|^{O(1)}}$ある計算可能な関数fに対して。

${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$かつその場合に限り${\displaystyle {\textsf {P}}={\textsf {NP}}}$[ ^{3 ]​}

問題がパラNP困難であるとは、それが${\displaystyle {\textsf {NP}}}$-パラメータの定数値に対して既に困難です。つまり、固定されたkの「スライス」があり、${\displaystyle {\textsf {NP}}}$-難しい。パラメータ化された問題は${\displaystyle {\textsf {para-NP}}}$-hard はクラスに属しません${\displaystyle {\textsf {XP}}}$、 ない限り${\displaystyle {\textsf {P}}={\textsf {NP}}}$典型的な例としては、${\displaystyle {\textsf {para-NP}}}$-難しいパラメータ化問題は、色の数kによってパラメータ化されたグラフ彩色であり、これはすでに${\displaystyle {\textsf {NP}}}$-難しい${\displaystyle k=3}$（グラフ彩色#計算複雑性を参照）。

一般的に、複雑性クラスを定義する方法は、機械理論的と論理的という2つあります。機械理論では、クラスは、ある種の機械によって解決可能な決定問題の集合として定義されます。論理学では、クラスは、ある種の論理式によって定義可能な決定問題の集合として定義されます。

機械理論的には、パラメータ化された問題がW[w][d]クラスに属するのは、その問題が次のような fpt 還元によって解決できる場合である。

• 定数整数が存在する${\displaystyle w,d}$、したがって
• すべてのインスタンス${\displaystyle (x,k)}$fpt時間内に、横糸が最大w、深さが最大dであるブール回路に変換される。
• ${\displaystyle (x,k)\in L}$回路が重みkの適切な割り当てを持っている場合に限ります。

ここで「W」は「weight」を表していることがわかります。上記の定義では、${\displaystyle w,d}$独立している${\displaystyle (x,k)}$しかし、回路自体は${\displaystyle (x,k)}$、また、どちらかを変更すると変更される可能性があります${\displaystyle x}$または${\displaystyle k}$。

クラスW[w]は、それらの和集合として定義されます。$${\displaystyle W[w][1]\subset W[w][2]\subset \dots \subset W[w]:=\bigcup _{d\geq 1}W[w][d]}$$より簡潔に言うと、W[w]は、weftを持つインスタンス固有のブール回路のファミリーにfpt還元可能な問題の集合である。${\displaystyle \leq w}$そして深さは、問題固有の定数によって制限される。

緯糸wと深さdの正規化された回路は、最初の${\displaystyle d-w}$層には小さなゲートしか含まれておらず、最後の${\displaystyle w}$層には、ANDゲートとORゲートが交互に配置されています。結合法則とド・モルガンの法則を繰り返し適用することで、fpt時間で回路を正規化できます。したがって、一般性を失うことなく、正規化された回路のみを考慮すればよいことになります。^{[ 7 ]}

モデル理論的には、クラスW[t]は、fpt 還元可能な問題のクラスとして定義される。${\displaystyle \operatorname {p-MC} (\Sigma _{t,1})}$。

W階層はNPに含まれる階層ですが、 A階層は古典的な複雑性における多項式時間階層により近いものです。機械理論的には、A階層の問題は、特定の種類の交代型チューリングマシンによる計算にfpt還元可能な問題として定義されます。「A」は「交代型」を意味します。^{[ 6 ]}

モデル理論的には、クラスA[t]は fpt 還元可能な問題のクラスとして定義される。${\displaystyle \operatorname {p-MC} (\Sigma _{t})}$。

例えば、k-クリーク問題はモデル検査問題として定式化できる。この言語には単一の二項関係がある。${\displaystyle E}$、 どこ${\displaystyle E(x,y)}$手段 "${\displaystyle x,y}$エッジを共有する」。次に、有限モデル${\displaystyle A}$はグラフであり、k-クリークを持つのは、${\displaystyle A\models \phi _{k}}$、 どこ$${\displaystyle \phi _{k}:=\exists x_{1:k},\bigwedge _{1\leq i<j\leq n}E(x_{i},x_{j})}$$これは、k-クリーク問題が${\displaystyle A[1]}$。

問題がA[i]完全であるとは、それがA[i]であり、任意のA[i]問題が fpt-還元されてそれに帰着する場合をいう。

定義により、$${\displaystyle W[0]\subset W[1]\subset \cdots ,\quad W[i]\subset A[i],\quad A[0]\subset A[1]\subset \cdots }$$${\displaystyle {\mathsf {FPT}}=W[0]=A[0]}$:

• ${\displaystyle W[0]=A[0]}$以来${\displaystyle \Sigma _{0}}$量化子が全くないので、違いはありません${\displaystyle \Sigma _{0}}$そして${\displaystyle \Sigma _{0,1}}$。
• ${\displaystyle {\mathsf {FPT}}\subset W[0]}$あらゆるFPT問題に対して${\displaystyle L}$次のように簡単に fpt 削減できます: 問題を解く${\displaystyle (x,k)\in L}$fpt時間内に、正しいブール値を出力するだけの単純なYes/No回路を出力する。
• ${\displaystyle {\mathsf {FPT}}\supset W[0]}$任意の W[0] 問題に対して${\displaystyle L}$、そしてあらゆる問題事例${\displaystyle c\in L}$回路${\displaystyle c}$横糸は0で${\displaystyle \leq d}$深さ${\displaystyle d}$は固定されています。したがって、出力は最大で によって決定されます。${\displaystyle 2^{d}}$入力。その他の入力はすべて自由に使用できます。したがって、単純に総当たりで計算すれば、${\displaystyle 2^{2^{d}}}$可能な入力。ある入力が重みk'を持ち、回路の出力がTrueになる場合、その重みを満たすのに十分な入力がまだあるかどうかを確認します。${\displaystyle \#({\text{inputs of }}c)-2^{d}\geq k-k'}$。

${\displaystyle W[1]=A[1]}$[ ^{6 ]​}

直感的に言えば、W[1]クラスの問題は、次のような形式で解釈できます。ある局所的にチェック可能な特性を持つサイズkのオブジェクトは存在するか？数式で表すと、次のようになります。$${\displaystyle \bigvee _{u_{1},\dots ,u_{k}}({\text{object constructed according to }}u_{1},\dots ,u_{k}{\text{ has a certain local property}})}$$実際、W[1]はW[1, 2]に縮退し、これは次の形式のブール回路にfpt還元可能な問題のクラスである。${\displaystyle \bigwedge _{i}(x_{i,1}\lor x_{i,2})}$つまり、2 のファンインの多数の OR に対する大きな AND です。^{[ 8 ]}

W[1]完全問題の例としては、次のものがあります。 ^{[ 8 ]}

• 独立したセット
  • 入力: グラフG
  • パラメータ：整数k
  • 出力：Gがサイズkの独立集合を含むかどうか
• クリックス
  • 入力: グラフG
  • パラメータ：整数k
  • 出力：Gがサイズkのクリークを含むかどうか
• 二部構成の非遮断器
  • 入力：二部グラフ${\displaystyle (V_{1},V_{2},E)}$
  • パラメータ：整数k
  • 出力：部分集合が存在するかどうか${\displaystyle S\subset V_{1}}$サイズkの任意の${\displaystyle v\in V_{2}}$隣人がいる${\displaystyle u\not \in S}$。 言い換えると、${\displaystyle S}$ブロックしない${\displaystyle V_{2}}$。
• 重み - k 2-満足度
  • 入力:形式の連言標準式${\displaystyle \bigwedge _{i}(p_{i,1}\lor p_{i,2})}$ここで、i は節の範囲を移動する。
  • パラメータ：整数k
  • 出力：式に対して重みkを満たす割り当てが存在するかどうか。
• チューリングマシンの簡単な問題。
  • 入力: 非決定性チューリングマシンM、文字列x、整数k。
  • 出力： Mが最大kステップでxを受け入れるような計算経路が1つ存在するかどうか。

通常の非ブロッキング問題は FPT であることに注意してください。^{[ 9 ]}

非決定性チューリングマシンに関する注記。マシンは、標準的な定式化のいずれかで指定できます。通常は1テープチューリングマシンを考えますが、f ( k )テープ、さらにはf ( k )次元テープのf ( k )を許容しても、短いチューリングマシン問題はW[1]のままです。しかし、この拡張でも、 f ( k )テープアルファベットサイズへの制限はFPTです。重要なのは、マシンM自体が問題入力の一部であるため、入力サイズnはMの状態数よりも大きいということです。このようにして、チューリングマシンは次のいずれかを取ることができます。${\displaystyle n}$ステップごとの可能な計算パス、アクセス${\displaystyle n^{O(k)}}$時間k内に合計ステップ数。したがって、 W[1]がFPT内に明らかに含まれていないことがわかります。

独立集合問題は次のように符号化できる。各グラフが与えられたとき。${\displaystyle (V,E)}$その独立集合問題は、次のweft-1ブール回路によって符号化されます。$${\displaystyle \Phi _{\text{IS}}(V,E):=\bigwedge _{\{u,v\}\in E}(\neg x_{u}\lor \neg x_{v})}$$どこ${\displaystyle E}$はグラフのエッジの集合です。グラフがサイズkの独立集合を持つのは、そのブール回路に重みk の入力があり、出力が 1 になる場合のみです。

クリーク問題は次のようにコード化できます。$${\displaystyle \Phi _{\text{clique}}(V,E):=\bigwedge _{\{u,v\}\subset V,u\neq v,\{u,v\}\not \in E}(\neg x_{u}\lor \neg x_{v})}$$これは、辺を形成しない頂点のペアは選択できないことを確認するため、選択された頂点の集合は必ずクリークとなる。

短いチューリングマシンの問題は、チューリングマシンの計算トレースをブール式として符号化することでSATがNP完全であることを示すクック・レヴィンの定理と同じ証明方法を用いてブール式に変換できます。以下の証明は^{[ 8 ] [ 10 ]}からのものです。具体的には、命題変数を定義します。

• ${\displaystyle s_{t,i,j,a,b}}$: 時刻tにおいて、チューリングマシンは状態iにあり、状態jに遷移し、 a を読み込み、bを書き込む。
• ${\displaystyle y_{t,p,a,b}}$: 時刻tにおいて、テープ位置pは記号aを持ち、時刻(t+1)において、記号bを持つ。

インデックスのうち、時間tとテープ位置p の範囲は1:kです。チューリングマシンの状態i、j、遷移m、および記号a、bへのインデックスの範囲はマシン M の説明によって決定されますが、どちらも1:n の範囲内に制限されます。

次に、その式${\displaystyle \Phi _{{\text{STM}},k}(M,x)}$これは、以下の制約を強制する節の連言です。

• すべてのチューリングマシン状態遷移が非決定性遷移規則によって禁止されるわけではありません。これらは次のようになります。${\displaystyle s_{t,i,j,a,b}\to \neg s_{t+1,i',j',a',b'}}$、 言い換えると、${\displaystyle \neg s_{t,i,j,a,b}\lor \neg s_{t+1,i',j',a',b'}}$。 がある${\displaystyle O(kn^{4})}$そのような条項。
• チューリングマシンは同時に2つの状態に存在することはできず、同時に2つの状態遷移を行うこともできない。
• テープセルのすべての状態遷移は、非決定論的遷移規則によって禁止されるわけではない。
• テープセルの各状態は、同時に2つのシンボルを持つことはできません。
• 時刻0において、チューリングマシンは初期状態および初期位置から逸脱しておらず、xはテープ上に書き込まれていない。
• チューリングマシンは時刻kにおいて受理しない状態ではない。

チューリングマシンを通る計算トレースは、k 個の変数を設定することによって完全に指定されます。${\displaystyle s_{t,i,j,a,b}}$各時点でのチューリングマシンの状態遷移を示すために True に設定し、${\displaystyle k^{2}}$変数${\displaystyle y_{t,p,a,b}}$各時点でのテープ状態遷移を示すために True に設定します。これにより、短いチューリングマシンの問題は重みを見つける問題に縮小されます。${\displaystyle (k+k^{2})}$緯糸1、深さ2、反単調ブール回路への適切な割り当て。

W[2]の問題は直感的には次のような形式です。サイズkのオブジェクトを推測し、オブジェクトに対してローカル処理を実行し、次にグローバル処理を実行します。

W [2]完全問題の例としては、

• 与えられたグラフにサイズkの支配集合が含まれているかどうかを判定する。
• 与えられた非決定性マルチテープチューリングマシンがkステップ以内に受理するかどうかを判定する問題（「短いマルチテープチューリングマシン受理」問題）。重要な点として、分岐はnに依存することが許容され（W[1]変種と同様）、テープの数も同様である。別のW [2]完全定式化では、シングルテープチューリングマシンのみが許容されるが、アルファベットサイズはnに依存する可能性がある。

支配集合問題には次の式がある${\displaystyle \Psi _{\text{dom}}(V,E)=\bigwedge _{u\in V}\bigvee _{v\in \operatorname {Neighbor} [u]}x_{v}}$。

いくつかの問題は、計算的に一般的な形式であるにもかかわらず、W[i]完全であることが知られており、通常はパラメータ化複雑性理論自体の中で研究されています。経験的には、2013年現在、彼らが研究した自然発生的なパラメータ化問題のほぼすべてが、 W[0]完全、W[1]完全、またはW[2]完全であることが判明しています。通常、次のものが使用されます。^{[ 4 ]}

• 重み付きi正規化充足可能性: ^{[ 7 ] [ 4 ] :定理 23.2.1}負の可能性のある変数の AND の OR の AND として記述されたブール式が与えられ、${\displaystyle i+1}$交互にANDまたはORが重なった層の場合、 k個の変数をちょうど1に設定することで条件を満たすことができますか？
  • 証明の概略: 任意のW[i]回路は、連想法則とド・モルガンの分配法則を反復することで fpt 時間で正規化できるため、この問題はW[i]完全であることが示されます。
• i>0が偶数の 場合、
  • ${\displaystyle {\text{monotone-}}W[i]=W[i]}$。
  • 重み付き単調i -正規化充足可能性はW[i] -完全である。
  • 重み付き単調(i+1) -正規化された充足可能性はW[i]にあります。
• i>0が奇数の場合、
  • ${\displaystyle {\text{antimonotone-}}W[i]=W[i]}$
  • 重み付きアントノトーンi -正規化充足可能性はW[i] -完全です。
  • もし${\displaystyle i\geq 3}$すると、重み付き反単調(i+1) -正規化充足可能性はW[i]に含まれる。

これらの問題は、パラメータ化された複雑性の文脈以外では研究されないという意味で、本質的に「人工的」である。文献では、W[i]完全である自然発生的な問題はほとんど報告されていない。${\displaystyle i\geq 3}$:

• 関係データベースにおける包含関係の検出はW[3]完全である。
• サプライチェーンモデルにおける特定の問題は、W[3]完全またはW[4]完全である。^{[ 11 ]}

W *階層はW階層に似ていますが、深さを一定に保つのではなく、パラメータ化します。W *[t]クラスは、この問題にfpt還元可能な問題のクラスとして定義されます。^{[ 5 ]}

• 入力: 緯糸の長さが最大​​t、深さが最大​​kのブール回路、
• パラメータ: k
• 出力：ブール回路に重みkを満たす割り当てが存在するかどうか。

これはWと以下の関係にある：^{[ 4 ]}$${\displaystyle W^{*}[1]=W[1],\;W^{*}[2]=W[2],\;W[t]\subset W^{*}[t]\subset W[t+2],\quad \forall t\geq 1}$$AW階層は、W階層に交代を加えることによって得られます。AW [t]クラスは、この問題にfpt還元可能な問題のクラスとして定義されます。^{[ 5 ] [ 6 ]}

• 入力: 最大tの緯糸のブール回路、およびその入力の分割${\displaystyle I_{1}\cup I_{2}\cup \cdots \cup I_{r}}$
• パラメータ:${\displaystyle (r,k_{1},\dots ,k_{r})}$
• 出力: ブール回路が交互の重みの下で充足可能かどうか${\displaystyle (k_{1},\dots ,k_{r})}$条件。

交互に重なる重量${\displaystyle (k_{1},\dots ,k_{r})}$は次のように定義されます。

• 部分集合が存在する${\displaystyle J_{1}\subset I_{1}}$サイズの${\displaystyle k_{1}}$つまり、それらの入力を真に設定し、他の入力を偽に設定すると、
• 任意の部分集合に対して${\displaystyle J_{2}\subset I_{2}}$サイズの${\displaystyle k_{2}}$つまり、それらの入力を真に設定し、他の入力を偽に設定すると、
• ...
• ブール回路はTrueを出力する。

これは2人対戦ゲームと解釈でき、1人目のプレイヤーは回路の出力をTrueにしようとし、2人目のプレイヤーは回路の出力をFalseにしようとします。1人目のプレイヤーは、正確に設定することで動きます。${\displaystyle k_{1}}$入力${\displaystyle I_{1}}$を True に、その他を False にすると、2 番目のプレイヤーが次の操作を行います。${\displaystyle I_{2}}$など。回路は交互の荷重を受けています。${\displaystyle (k_{1},\dots ,k_{r})}$条件は、プレイヤー1が必勝戦略を持っている場合のみである。

階層構造が崩壊することが判明した。${\displaystyle AW[1]=AW[2]=\cdots }$そのため、文献ではそれらを表す一般的な記号が用いられている。${\displaystyle AW[\ast ]:=AW[1]=AW[2]=\cdots }$。

• Downey, Rod G. ; Fellows, Michael R. (1999). Parameterized Complexity . Springer. doi : 10.1007/978-1-4612-0515-9 . ISBN 978-0-387-94883-6。
• ニーダーマイヤー、ロルフ(2006)。固定パラメータアルゴリズムへの招待。オックスフォード大学出版局。ISBN 978-0-19-856607-6。入門書。
• Flum, Jörg ; Grohe, Martin (2006). Parameterized Complexity Theory . Springer. doi : 10.1007/3-540-29953-X . ISBN 978-3-540-29952-3。1999年版教科書の改訂版序文。
• Downey, Rodney G.; Fellows, Michael R. (2013). Fundamentals of Parameterized Complexity . Texts in Computer Science. London: Springer London. doi : 10.1007/978-1-4471-5559-1 . ISBN 978-1-4471-5558-4。1999年版教科書以降の発展について解説するために書かれた、入門書ではない教科書。
• サイガン、マレック。フォミン、ヒョードル V.コワリク、ルカシュ。ロクシュタノフ、ダニエル。マルクス、ダニエル。ピリップチュク、マルシン。ピリチュク、ミハル。サウラブ、サケット (2015)。パラメータ化されたアルゴリズム。スプリンガー。ISBN 978-3-319-21274-6。