指数時間仮説

計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。

定義
k-SATは一つの節に含まれる変数が高々k個であるような連言標準形の論理式が、ある真偽値の割り当てによって真となるようにできるかどうかチェックするという問題である。
各整数 k ≥ 2に対して、実数skをk-SATをO(2δn)-時間で解くアルゴリズムが存在するような実数δの下限とする(nは与えられたk-SATのインスタンスに含まれる変数の個数)。このとき、2-SATは多項式時間で解けるためs2 = 0である。指数時間仮説は、すべてのk > 2に対してsk > 0であるという予想である。明らかに、s3 ≤ s4 ≤ ...である。そのためこれはs3 > 0と同値である(残りの skが正であることはすぐにこれから言える)。

指数時間仮説を、「3-SATは2o(n)時間で解けない」という少し弱い形で定義している文献もある。もし3-SATを2o(n)時間で解くアルゴリズムが存在すれば、明らかにs3は0である。しかし、これは「0に収束する数列δiが存在して、各アルゴリズムがO(2δin)時間で動くような3-SATのアルゴリズムの列が存在するが、種類が高速に増大するので最適なものを選ぶことができない」という現在の知識と矛盾しない。

数列s3, s4, ...は上界1を持つ単調増加数列なので、極限値s∞が存在する。強指数時間仮説(Strong exponential time hypothesis)は、極限値s∞ が1に等しいという予想である。

注釈

参考文献
.
.
.
.
.
.
.
.
.
.
.
.

計算複雑性理論
予想
数学に関する記事