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

コンピュータサイエンスにおいて、パラメータ化された複雑性は、入力または出力の複数のパラメータに関する固有の難しさに基づいて計算問題を分類することに焦点を当てた計算複雑性理論の一分野です。問題の複雑性は、それらのパラメータの関数として測定されます。これにより、問題の複雑性が入力のビット数の関数としてのみ測定される従来の設定よりも細かいスケールでNP 困難な問題を分類できます。これは、Gurevich、Stockmeyer、Vishkin (1984) で初めて実証されたようです。パラメータ化された複雑性に関する最初の体系的な研究は、Downey と Fellows (1999) によって行われました。

P ≠ NPという仮定の下では、複雑度が入力サイズのみで測定される場合には超多項式の実行時間を必要とするが、入力サイズに対しては多項式で、パラメータkに対しては指数関数的またはそれより悪い時間で計算可能な自然問題が多数存在します。したがって、k が小さな値に固定され、 kに対する関数の増加が比較的小さい場合、そのような問題は、従来の「扱いにくい」分類にもかかわらず、依然として「扱いやすい」と見なすことができます。

NP 完全問題、あるいはNP 困難問題に対する効率的で正確かつ決定論的なアルゴリズムは、入力パラメータが固定されていない場合は、存在しそうにないと考えられます。これらの問題に対する既知のアルゴリズムはすべて、入力の合計サイズに対して指数関数的(つまり、超多項式的) な時間を必要とします。ただし、一部の問題は、固定パラメータのサイズに対してのみ指数関数的であり、入力のサイズに対しては多項式的なアルゴリズムで解くことができます。このようなアルゴリズムは、固定パラメータの定数値に対して問題を効率的に (つまり、多項式時間で) 解くことができるため、固定パラメータ扱いやすい(FPT) アルゴリズムと呼ばれます。

いくつかのパラメータkが固定されている問題は、パラメータ化された問題と呼ばれます。このような FPT アルゴリズムを可能にするパラメータ化された問題は、固定パラメータの扱いやすい問題と呼ばれ、 FPTクラスに属します。パラメータ化された複雑性の理論の初期の名前は、固定パラメータの扱いやすさでした。

多くの問題は、次のような形式をとります。オブジェクトxと非負の整数kが与えられたとき、x はkに依存する何らかの特性を持つでしょうか。たとえば、頂点カバー問題の場合、パラメータはカバー内の頂点の数になります。多くのアプリケーション、たとえばエラー訂正をモデル化する場合、パラメータは合計入力サイズに比べて「小さい」と想定できます。その場合、kのみで指数関数的であり、入力サイズでは指数関数的ではないアルゴリズムを見つけるのは困難です。

このように、パラメータ化された複雑さは2 次元の複雑さの理論として考えることができます。この概念は次のように形式化されます。

パラメータ化された問題は言語 であり、 は有限のアルファベットです。2 番目のコンポーネントは、問題のパラメータと呼ばれます。${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$${\displaystyle \Sigma }$

パラメータ化された問題L は、質問「?」が実行時間 で決定できる場合、固定パラメータで扱いやすい問題です。ここで、 fはkのみに依存する任意の関数です。対応する複雑性クラスはFPTと呼ばれます。${\displaystyle (x,k)\in L}$${\displaystyle f(k)\cdot |x|^{O(1)}}$

例えば、頂点被覆問題を時間内に解くアルゴリズムがあります。 ^[1]ここで、nは頂点の数、kは頂点被覆のサイズです。これは、頂点被覆が、解のサイズをパラメータとして固定パラメータで扱いやすいことを意味します。 ${\displaystyle O(kn+1.274^{k})}$

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

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

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

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

FPT は、 fpt 削減と呼ばれるパラメーター化された削減の概念の下で閉じています。このような削減は、ある問題のインスタンスを別の問題の同等のインスタンスに変換し( を使用)、が多項式で ある場合に で計算できます。${\displaystyle (x,k)}$${\displaystyle (x',k')}$${\displaystyle k'\leq g(k)}$${\displaystyle f(k)\cdot p(|x|)}$${\displaystyle p}$

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

W階層は、計算複雑性クラスの集合です。パラメータ化された問題は、すべてのインスタンスが(fpt 時間で) 最大でi の横糸を持つ組み合わせ回路に変換でき、入力に 1 をちょうどk個の入力に割り当てる満足のいく割り当てがある場合に限り、クラス W [ i ] に属します。横糸は、入力から出力までの任意のパス上でファンインが 2 を超える論理ユニットの最大数です。パス上の論理ユニットの合計数 (深さと呼ばれる) は、問題のすべてのインスタンスに当てはまる定数によって制限される必要があります。 ${\displaystyle (x,k)}$${\displaystyle (x,k)\in L}$

すべての に対しておよびであることに注意してください。W階層内のクラスも fpt 削減の下で閉じています。 ${\displaystyle {\mathsf {FPT}}=W[0]}$${\displaystyle W[i]\subseteq W[j]}$${\displaystyle i\leq j}$

W [ i ]の完全な問題は、重み付きi正規化充足可能性です。^[3]否定される可能性のある変数の AND の OR の AND として記述されたブール式があり、AND または OR のレイヤー (およびAND と OR のi回の交代) がある場合、 k個の変数を 1 に設定することで満たすことができますか? ${\displaystyle i+1}$

多くの自然な計算問題は、より低いレベルであるW [1]とW [2]を占めます。

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

• 与えられたグラフにサイズkのクリークが含まれているかどうかを決定する
• 与えられたグラフにサイズkの独立集合が含まれているかどうかを決定する
• 与えられた非決定性単一テープチューリングマシンがkステップ以内で受け入れるかどうかを決定する (「短いチューリングマシン受け入れ」問題)。これは、 f ( k ) テープ、さらには f ( k ) 次元テープを持つ非決定性チューリングマシンにも適用されますが、この拡張があっても、 f ( k )テープアルファベットサイズへの制限は固定パラメータで扱い可能です。重要なのは、各ステップでのチューリングマシンの分岐が、入力のサイズnに依存できることです。このようにして、チューリングマシンはn ^{O( k )}計算パスを探索できます。

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

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

${\displaystyle W[t]}$は、重み付きWeft -t -Depth- d SAT問題の族を使用して定義できます。 は、この問題にfpt還元されるパラメーター化された問題のクラスであり、です。 ${\displaystyle d\geq t}$${\displaystyle W[t,d]}$${\displaystyle W[t]=\bigcup _{d\geq t}W[t,d]}$

ここで、Weighted Weft- t -Depth- d SAT は次の問題です。

• 入力: 深さが最大​​d、横糸が最大tのブール式と数値k。深さは、ルートからリーフまでの任意のパス上のゲートの最大数であり、横糸は、ルートからリーフまでの任意のパス上のファンインが少なくとも 3 つのゲートの最大数です。
• 質問: この式には、ハミング重みが正確にk に割り当てられた満足のいく値がありますか?

問題Weighted t -Normalize SATはfpt-reductionsの下で完全であることが示せます。^[4] ここで、Weighted t -Normalize SATは次の問題です。 ${\displaystyle t\geq 2}$${\displaystyle W[t]}$

• 入力: 深さが最大​​tで、上部に AND ゲートがあり、数値kであるブール式。
• 質問: この式には、ハミング重みが正確にk に割り当てられた満足のいく値がありますか?

W [ P ] は、 （k制限チューリングマシン）の計算において最大で非決定的な選択を行う非決定性時間チューリングマシンによって決定できる問題のクラスです。Flum & Grohe（2006） ${\displaystyle h(k)\cdot {|x|}^{O(1)}}$${\displaystyle O(f(k)\cdot \log n)}$${\displaystyle (x,k)}$

FPT は W[P] に含まれることが知られており、その包含は厳密であると考えられています。ただし、この問題を解決することは、 P 対 NP問題の解決を意味します。

パラメータ化されていない計算複雑性とのその他の関係としては、回路の充足可能性が時間 で決定できる場合のみFPT がW [ P ] に等しいこと、または、非決定的選択を使用する非決定的多項式時間チューリングマシンによって認識されるすべての言語がPに含まれるような計算可能で非減少で無制限の関数 f が存在する場合のみ FPT がW [ P ]に等しいことが挙げられます 。 ${\displaystyle \exp(o(n))m^{O(1)}}$${\displaystyle f(n)\log n}$

W [ P ] は、 n個の項目の集合Sがあり、特定の特性を持つサイズkのサブセットを見つけようとする問題のクラスとして大まかに考えることができます。選択肢は、バイナリで保存されたk個の整数のリストとしてエンコードできます。これらの数値の最大値はnであるため、数値ごとにビットが必要です。したがって、選択肢をエンコードするには合計ビットが必要です。したがって、非決定的な選択肢 を持つサブセットを選択できます。${\displaystyle T\subset S}$${\displaystyle \lceil \log _{2}n\rceil }$${\displaystyle k\cdot \lceil \log _{2}n\rceil }$${\displaystyle T\subset S}$${\displaystyle O(k\cdot \log n)}$

XP は、何らかの計算可能な関数fについて時間内に解決できるパラメータ化された問題のクラスです。これらの問題は、固定された k の各「スライス」に多項式アルゴリズムがあるという意味でスライスワイズ多項式と呼ばれますが、各 k の指数は異なる場合があります。これを、k の値ごとに異なる定数前因子を許可するだけの FPT と比較してください。XP には FPT が含まれており、この包含は対角化によって厳密であることがわかっています。 ${\displaystyle n^{f(k)}}$

パラNPは、ある計算可能な関数fに対して非決定性アルゴリズムで時間内に解くことができるパラメータ化された問題のクラスである。のときのみ であることが知られている。^[5]${\displaystyle f(k)\cdot |x|^{O(1)}}$${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$${\displaystyle {\textsf {P}}={\textsf {NP}}}$

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

A階層はW階層に似た計算複雑性クラスの集合です。ただし、W階層はNPに含まれる階層ですが、A階層は古典的な複雑性からの多項式時間階層をより忠実に模倣しています。A[1] = W[1]が成り立つことが知られています。

• パラメータ化された近似アルゴリズム。最適化問題の場合、FPT 時間で実行されるアルゴリズムによってソリューションが近似される場合があります。

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006).頂点カバーのパラメータ化された上限の改善。コンピュータサイエンスの数学的基礎。Vol. 4162。ベルリン、ハイデルベルク：Springer。pp. 238–249。CiteSeerX 10.1.1.432.831。doi  :10.1007 / 11821069_21。ISBN 978-3-540-37791-7。
• サイガン、マレック。フォミン、ヒョードル V.コワリク、ルカシュ。ロクシュタノフ、ダニエル。マルクス、ダニエル。ピリップチュク、マルシン。ピリチュク、ミハル。サウラブ、サケット (2015)。パラメータ化されたアルゴリズム。スプリンガー。 p. 555.ISBN​ 978-3-319-21274-6。
• ダウニー、ロッド G. ;フェローズ、マイケル R. (1999)。パラメータ化された複雑性。シュプリンガー。ISBN 978-0-387-94883-6。
• フルム、ヨルグ。グローエ、マーティン(2006)。パラメータ化された複雑性理論。スプリンガー。ISBN 978-3-540-29952-3。
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019).カーネル化: パラメータ化された前処理の理論. Cambridge University Press. p. 528. doi :10.1017/9781107415157. ISBN 978-1107057760. S2CID  263888582。
• Gurevich, Yuri; Stockmeyer, Larry; Vishkin, Uzi (1984)。ほぼ木であるグラフ上の NP 困難問題の解決と施設配置問題への応用。Journal of the ACM。p. 459-473。
• ニーダーマイヤー、ロルフ(2006)。固定パラメータ アルゴリズムへの招待。オックスフォード大学出版局。ISBN 978-0-19-856607-62008年9月24日時点のオリジナルよりアーカイブ。
• Grohe, Martin (1999)。「記述的およびパラメータ化された複雑性」。コンピュータサイエンスロジック。コンピュータサイエンスの講義ノート。第 1683 巻。Springer Berlin Heidelberg。pp. 14–31。CiteSeerX 10.1.1.25.9250。doi :  10.1007 /3-540-48168-0_3。ISBN 978-3-540-66536-6。
• コンピュータジャーナル。第 51 巻、第 1 号および第 3 号 (2008 年)。コンピュータジャーナル。パラメータ化された複雑性に関する 2 部構成の特別号で、15 件の調査記事、書評、およびゲスト編集者 R. Downey、M. Fellows、および M. Langston による序文が掲載されています。

• パラメータ化された複雑さに関するWiki
• パラメータ化された問題の概要