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