指数時間仮説

計算複雑性理論において、指数時間仮説は、Impagliazzo & Paturi (1999) によって定式化された未証明の計算困難性仮説である。これは、 3-CNF ブール式の充足可能性は、指数時間未満で解くことができないというものである。より正確には、この仮説の通常の形式は、この問題を正しく解くすべてのアルゴリズムが少なくとも の時間を必要とするような数の存在を主張するものである。指数時間仮説が正しい場合、P ≠ NPを意味するが、これはより強い主張である。これは、多くの計算問題は、そのうちの 1 つに指数時間未満アルゴリズムがある場合、すべてに指数時間未満アルゴリズムがあり、これらの問題に対する多くの既知のアルゴリズムは、最適またはほぼ最適な時間計算複雑性を持つという意味で、複雑さにおいて同等であることを意味する。^[1]${\displaystyle 2^{o(n)}}$${\displaystyle s_{3}>0}$${\displaystyle 2^{s_{3}n}.}$

-SAT問題はブール式の充足可能性問題の一種で、問題への入力は、節ごとに最大 個の変数を含む、連言正規形 (つまり、変数とその否定の論理積)のブール式です。目標は、変数にブール値を割り当てることによって、この式を true にできるかどうかを判断することです。2 -SAT には線形時間アルゴリズムがありますが、より大きい に対する既知のアルゴリズムはすべて指数時間かかり、指数関数の底は に依存します。たとえば、確率アルゴリズムWalkSAT は、平均時間 で-SAT を解くことができます。ここで、 は、特定の-SATインスタンス内の変数の数です。^[2]各整数に対して、を時間で-SAT を解くことができる最小の数 と定義します。この最小値は、より優れたアルゴリズムのシーケンスで時間境界がそれに応じてより小さく指数関数的に増加する場合は存在しない可能性があります。その場合、 を-SAT が時間以内に解ける実数の下限と定義します。より大きな数の問題は簡単になるはずがないため、これらの数は と並べられ、 WalkSAT により最大で になります。指数時間仮説は、それらはすべてゼロでない、またはそれと同等に、それらの最小値である はゼロでないという推測です。^[1]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$$${\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}$$${\displaystyle n}$${\displaystyle k}$ ${\displaystyle k\geq 3}$${\displaystyle s_{k}}$${\displaystyle k}$${\displaystyle 2^{s_{k}n+o(n)}}$${\displaystyle s_{k}}$${\displaystyle \delta}$${\displaystyle k}$${\displaystyle O(2^{\delta n})}$${\displaystyle k}$${\displaystyle s_{3}\leq s_{4}\leq \cdots }$$${\displaystyle s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.}$$${\displaystyle s_{3}}$

いくつかの情報源では、指数時間仮説は、3-SAT は時間で解くことができないというやや弱い主張であると定義されています。${\displaystyle 2^{o(n)}}$時間${\displaystyle 2^{o(n)}}$で 3-SAT を解くアルゴリズムが存在する場合、はゼロになります。ただし、一連の数値の実行時間がゼロに近づく 3-SAT アルゴリズムのシーケンスが存在する可能性があるが、これらのアルゴリズムの説明が急速に増えているため、単一のアルゴリズムでは最も適切なものを自動的に選択して実行できないことは、現在の知識と一致しています。これが事実である場合、時間で実行される単一のアルゴリズムが存在しないにもかかわらず、はゼロになります。^[3]指数時間仮説に関連するバリエーションは、非一様指数時間仮説であり、時間で 3-SAT を解くことができるアルゴリズムのファミリ (アドバイスの精神で、入力の長さごとに 1 つ)は存在しないと仮定します。^[4]${\displaystyle s_{3}}$${\displaystyle O(2^{\delta _{i}n})}$${\displaystyle \delta_{i}}$${\displaystyle s_{3}}$${\displaystyle 2^{o(n)}}$${\displaystyle 2^{o(n)}}$

数は1を超える単調な数列を形成するため、必ず極限に収束する。強い指数時間仮説（SETH）は、次のような仮説である。^[5]${\displaystyle s_{3},s_{4},\dots }$$${\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}$$${\displaystyle s_{\infty}=1}$

任意の有限の に対してが等しくなることは不可能です。Impagliazzo、Paturi & Zane (2001) が示したように、となる定数が存在します。したがって、指数時間仮説が正しい場合、とは異なるに対しての値は無限に存在する必要があります。^[6]${\displaystyle s_{k}}$${\displaystyle s_{\infty}}$${\displaystyle k}$${\displaystyle \alpha}$${\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}$${\displaystyle k}$${\displaystyle s_{k}}$${\displaystyle s_{k+1}}$

この分野で重要なツールは、Impagliazzo、Paturi & Zane (2001) のスパース化補題です。これは、すべてのに対して、${\displaystyle \epsilon >0}$任意の-CNF式をより単純な-CNF式に置き換えることができることを示しています。この式では、各変数が定数回のみ出現し、したがって節の数は線形です。スパース化補題は、特定の式で空でない共通交差を持つ節の大きなセットを繰り返し見つけ、その式を 2 つのより単純な式に置き換えることによって証明されます。2 つの式のうちの 1 つは、これらの各節をそれらの共通交差で置き換え、もう 1 つは各節から交差を削除したものです。スパース化補題を適用し、新しい変数を使用して節を分割すると、それぞれが線形数の変数を持つ 3-CNF 式の集合が得られ、これらの 3-CNF 式の少なくとも 1 つが満たされる場合にのみ、元の-CNF式が満たされます。したがって、3-SATが指数関数的時間で解けるのであれば、この縮約法を使って-SATも指数関数的時間で解くことができる。同様に、任意のに対してであれば となり、指数時間仮説は真となる。^{[7] [6]}${\displaystyle k}$${\displaystyle O(2^{\varepsilon n})}$${\displaystyle k}$${\displaystyle O(2^{\varepsilon n})}$${\displaystyle k}$${\displaystyle k}$${\displaystyle s_{k}>0}$${\displaystyle k>0}$${\displaystyle s_{3}>0}$

数列の極限値 は最大で に等しく、ここで は節の長さの制限のない連言標準形式の充足可能性を時間で解決できる数の下限です。したがって、強い指数時間仮説が正しい場合、すべての可能な真理値の割り当てを総当たりで探すよりも大幅に高速な一般的な CNF 充足可能性のアルゴリズムは存在しません。ただし、強い指数時間仮説が失敗した場合でも、 が 1に等しくなる可能性はあります。^[8]${\displaystyle s_{\infty}}$${\displaystyle s_{k}}$${\displaystyle s_{\operatorname {CNF} }}$${\displaystyle s_{\operatorname {CNF} }}$${\displaystyle \delta}$${\displaystyle O(2^{\delta n})}$${\displaystyle s_{\operatorname {CNF} }}$

指数時間仮説は、複雑性クラスSNPの他の多くの問題には、ある定数よりも実行時間が速いアルゴリズムが存在しないことを示唆している。これらの問題には、グラフk色可能性、ハミルトン閉路の発見、最大クリーク、最大独立集合、および-頂点グラフ上の頂点カバーが含まれる。逆に、これらの問題のいずれかに指数以下のアルゴリズムが存在する場合、指数時間仮説は誤りであることが示される可能性がある。^{[7] [6]}${\displaystyle c^{n}}$${\displaystyle c}$${\displaystyle n}$

対数サイズのクリークまたは独立集合を多項式時間で見つけられる場合、指数時間仮説は誤りである。したがって、そのような小さなサイズのクリークまたは独立集合を見つけることがNP完全である可能性は低いが、指数時間仮説はこれらの問題が非多項式であることを意味する。^{[7] [9]}より一般的には、指数時間仮説は、時間のサイズのクリークまたは独立集合を見つけることは不可能であることを意味する。^{[10]指数時間仮説は、} k -SUM問題（実数が与えられたとき、それらの和がゼロになるものを見つける）を時間で解くことは不可能であることを意味する。強い指数時間仮説は、時間よりも速く-頂点支配集合 を見つけることは不可能であることを意味する。^[8]${\displaystyle k}$${\displaystyle n^{o(k)}}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n^{o(k)}}$${\displaystyle k}$${\displaystyle n^{ko(1)}}$

指数時間仮説は、トーナメント上の重み付きフィードバックアークセット問題には実行時間のパラメータ化されたアルゴリズムがないことも意味します。ただし、実行時間のパラメータ化されたアルゴリズムは存在します。^[11]${\textstyle O(2^{o({\sqrt {\オペレータ名 {OPT} }})}n^{O(1)})}$${\textstyle O(2^{O({\sqrt {\オペレーター名 {OPT} }})}n^{O(1)})}$

強い指数時間仮説は、木幅が制限されたグラフ上のいくつかのグラフ問題のパラメータ化された複雑性に厳しい境界を導きます。特に、強い指数時間仮説が正しい場合、木幅のグラフ上で独立集合を見つけるための最適時間境界は、支配集合問題の最適時間は、最大カットの最適時間は、-色付けの最適時間は です。^[12]同様に、これらの実行時間の改善は、強い指数時間仮説を偽とすることになります。^[13]指数時間仮説はまた、エッジクリークカバーの固定パラメータの扱いやすいアルゴリズムは、パラメータに対して二重指数依存性を持つ必要があることも意味します。^[14]${\displaystyle w}$ ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$${\textstyle {\bigl (}3-o(1){\bigr )}^{w}n^{O(1)}}$ ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$${\displaystyle k}$ ${\textstyle {\bigl (}ko(1){\bigr )}^{w}n^{O(1)}}$

通信複雑性における3 者間集合の非重複問題では、ある範囲の整数の 3 つの部分集合が指定され、3 つの通信当事者はそれぞれ 3 つの部分集合のうち 2 つを知っている。目標は、当事者が共有通信チャネルで互いにできるだけ少ないビットを送信し、当事者の 1 つが 3 つの集合の共通部分が空か空でないか判断できるようにすることである。単純な- ビット通信プロトコルは、3 者のうちの 1 者が、その当事者が知っている 2 つの集合の共通部分を記述するビットベクトルを送信し、その後、残りの 2 者のいずれかが共通部分が空かどうかを判断できるようにするものである。ただし、通信と計算で問題を解決するプロトコルが存在する場合、任意の固定定数に対して-SAT を時間内に解決するアルゴリズムに変換でき、強い指数時間仮説に違反する可能性がある。したがって、強い指数時間仮説は、3 者間集合の非重複に関する単純なプロトコルが最適であるか、またはより優れたプロトコルには指数量の計算が必要であることを意味している。^[8]${\displaystyle [1,m]}$${\displaystyle m}$${\displaystyle o(m)}$${\displaystyle 2^{o(m)}}$${\displaystyle k}$${\displaystyle O(1.74^{n})}$${\displaystyle k}$

指数時間仮説が正しい場合、3-SAT には多項式時間アルゴリズムがないため、P ≠ NPとなります。より強い言い方をすると、この場合、3-SAT には準多項式時間アルゴリズムさえ存在しないため、 NP は QP のサブセットにはなり得ません。ただし、指数時間仮説が間違っている場合、P 対 NP 問題には影響がありません。パディングの議論により、 に対する最良実行時間が の形式である NP 完全問題の存在が証明され、3 -SAT の最良実行時間がこの形式である場合、 P は NP と等しくありませんが (3-SAT は NP 完全であり、この時間制限は多項式ではないため)、指数時間仮説は誤りです。 ${\textstyle O(2^{n^{c}})}$ ${\displaystyle c<1}$

パラメータ化された複雑性理論では、指数時間仮説は、最大クリークに対する固定パラメータで扱いやすいアルゴリズムが存在しないことを意味するため、W[1] ≠ FPTであることも意味します。^[10]この含意が逆転できるかどうか、つまりW[1] ≠ FPT は指数時間仮説を意味するかどうかは、この分野における重要な未解決問題です。パラメータ化された複雑性クラスの階層は M 階層と呼ばれ、すべてのに対して、${\displaystyle i}$ という意味で W 階層をインターリーブします。たとえば、パラメータを持つ-頂点グラフでサイズ の頂点カバーを見つける問題は、M[1] に対して完全です。指数時間仮説は、 M[1] ≠ FPTというステートメントと同等であり、 に対してであるかどうかという問題も未解決です。^[3]${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]}$${\displaystyle k\log n}$${\displaystyle n}$${\displaystyle k}$${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]}$${\displaystyle i>1}$

また、強い指数時間仮説のバリエーションの失敗から複雑性のクラスの分離まで、逆方向の含意を証明することも可能である。ウィリアムズ (2010) が示すように、ある超多項式的に増加する関数に対してブール回路の充足可能性を時間内に解決するアルゴリズムが存在する場合、NEXPTIMEはP/polyのサブセットではない。ウィリアムズは、 アルゴリズムが存在し、P/poly で NEXPTIME をシミュレートする回路の族も存在する場合、 アルゴリズム を回路と合成して、NEXPTIME 問題を非決定的に短時間でシミュレートすることができ、時間階層定理に違反することを示す。したがって、 アルゴリズム の存在は、回路の族が存在しないことを証明し、これら 2 つの複雑性のクラスの分離を証明する。 ^[15]${\displaystyle A}$${\displaystyle 2^{n}/f(n)}$${\displaystyle f}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$

• サビッチの定理は、同様の指数ギャップが空間計算量には当てはまらないことを示している。