準多項式時間

計算複雑性理論およびアルゴリズム解析において、アルゴリズムの時間計算量が準多項式的に制限されている場合、そのアルゴリズムは準多項式時間であると言われる。つまり、定数が存在するはずである。${\displaystyle c}$アルゴリズムの最悪実行時間は、入力サイズが${\displaystyle n}$、の上限は次の形式 である。$${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}$$

準多項式時間アルゴリズムを用いた決定問題は、多項式時間でもなく、NP困難である可能性も低いことから、NP中間問題となる自然な候補である。

複雑性クラスQPは、準多項式時間アルゴリズムを持つすべての問題から構成されます。DTIMEの観点からは、次のように定義できます。^{[ 1 ]}

${\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}$

準多項式時間アルゴリズムの初期の例としては、Adleman–Pomerance–Rumely素数判定法がある。^{[ 2 ]}しかし、ある数が素数かどうかを判定する問題は、その後、 AKS素数判定法という多項式時間アルゴリズムが存在することが示された。^{[ 3 ]}

場合によっては、準多項式時間境界が指数時間仮説または関連する計算困難性仮定の下で最適であることが証明されることがあります。例えば、以下の問題ではこれが当てはまります。

• 双曲平面上の単位円盤の集合から最大の互いに素な部分集合を見つける問題は、時間で解くことができる。${\displaystyle n^{O(\log n)}}$、そして時間を要する${\displaystyle n^{\Omega (\log n)}}$指数時間仮説の下で。^{[ 4 ]}
• 与えられたグラフの誘導部分グラフとして現れない、頂点数が最小のグラフを見つける問題は、時間で解くことができる。${\displaystyle n^{O(\log n)}}$、そして時間を要する${\displaystyle n^{\Omega (\log n)}}$指数時間仮説の下で。^{[ 5 ]}
• トーナメントにおける最小支配集合の探索。これは、トーナメントの頂点のサブセットであり、他のすべての頂点に少なくとも1つの有向辺を持つものです。これは時間で解くことができます。${\displaystyle n^{O(\log n)}}$、そして時間を要する${\displaystyle n^{\Omega (\log n)}}$指数時間仮説の下で。^{[ 6 ]}
• 集合族のヴァプニク・チェルヴォネンキス次元を計算する。これは最大の集合のサイズである。${\displaystyle S}$（必ずしも家族内ではない）家族によって破壊される、つまり各サブセットは${\displaystyle S}$交差することで形成できる${\displaystyle S}$家族の一員と。時間内に解決できる。${\displaystyle n^{O(\log n)}}$[ ^{7 ]}時間も^必要${\displaystyle n^{(\log n)^{1/3-o(1)}}}$指数時間仮説の下で。^{[ 8 ]}

最もよく知られているアルゴリズムが準多項式時間で解けるその他の問題には、以下のようなものがある。

• 植え付けクリーク問題とは、ランダムグラフの頂点のサブセットのすべてのペア間にエッジを追加することによってグラフが変更されたかどうかを判定する問題である。^{[ 9 ]}
• 単調双対化、論理式を連言標準形と選言標準形の間で変換するいくつかの同等の問題、集合族のすべての最小ヒットセットを列挙する問題、または集合族のすべての最小セットカバーを列挙する問題があり、時間計算量は入力と出力のサイズを合わせたもので測定されます。^{[ 10 ]}
• パリティゲームは、色付き有向グラフのエッジに沿ってトークンを渡すゲームです。^{[ 11 ]}これらのゲームに対する準多項式アルゴリズムを提示した論文は、2021年のネロード賞を受賞しました。^{[ 12 ]}
• 円グラフの3色彩色。これらは円の弦の交差グラフです。一般的に、最適な彩色を見つけることはNP困難であり、4色で彩色できるかどうかを判定することもNP困難ですが、3色での彩色は時間で見つけることができます。${\displaystyle n^{O(\log n)}}$[ ^{13 ]​}

準多項式時間アルゴリズムが発表されているものの、完全な形で公開されていない問題には、以下のようなものがある。

• グラフ同型性問題とは、頂点のラベルを変更することで2つのグラフを等しくできるかどうかを判定する問題で、2015年に発表され、2017年にラースロー・ババイによって更新された。^{[ 14 ]}
• 結び目図が解けた結び目を表しているかどうかを認識する解けた結び目問題は、 2021年にマーク・ラッケンビーによって発表された。^{[ 15 ]}

準多項式時間は、近似アルゴリズムの研究にも使用されています。特に、準多項式時間近似スキーム（QPTAS）は、実行時間が多項式ではなく準多項式である多項式時間近似スキームの変種です。QPTAS の問題には、最小重み三角分割^{[ 16 ]}、ディスクの交差グラフ上の最大クリークの探索^{[ 17 ]} 、および、与えられた独立した確率で一部のエッジが失敗した場合にハイパーグラフが非連結になる確率の決定^{[ 18 ]などがあります。}

さらに言えば、近似ナッシュ均衡を見つける問題はQPTASを持つが、指数時間仮説の下ではPTASを持つことはできない。^{[ 19 ]}