指数時間仮説
k-SATは一つの節に含まれる変数が高々k個であるような連言標準形の論理式が、ある真偽値の割り当てによって真となるようにできるかどうかチェックするという問題である。 各整数 k ≥ 2に対して、実数skをk-SATをO(2)-時間で解くアルゴリズムが存在するような実数δの下限とする(nは与えられたk-SATのインスタンスに含まれる変数の個数)。このとき、2-SATは多項式時間で解けるためs2 = 0である。指数時間仮説は、すべてのk > 2に対してsk > 0であるという予想である。明らかに、s3 ≤ s4 ≤ ...である。そのためこれはs3 > 0と同値である(残りの skが正であることはすぐにこれから言える)。
指数時間仮説を、「3-SATは2時間で解けない」という少し弱い形で定義している文献もある。もし3-SATを2時間で解くアルゴリズムが存在すれば、明らかにs3は0である。しかし、これは「0に収束する数列δiが存在して、各アルゴリズムがO(2)時間で動くような3-SATのアルゴリズムの列が存在するが、種類が高速に増大するので最適なものを選ぶことができない」という現在の知識と矛盾しない。
数列s3, s4, ...は上界1を持つ単調増加数列なので、極限値s∞が存在する。強指数時間仮説(Strong exponential time hypothesis)は、極限値s∞ が1に等しいという予想である。