この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "指数関数時間" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年5月)

指数関数時間（しすうかんすうじかん）あるいは指数時間（しすうじかん）とは、計算理論において指数関数を用いてあらわされる計算時間。計算複雑性理論では指数関数時間で解ける判定問題のクラスのことをクラス EXPTIME（あるいは EXP）という。

一般に指数関数時間やそれ以上のアルゴリズムは時間がかかりすぎるので実用には適さない。そのようなアルゴリズムは特殊な場合にしか使われない。

定義

計算量の問題で指数関数時間のアルゴリズムという場合には、解くべき問題のサイズ n に対して処理時間が多項式時間では収まらず指数関数的に増加してしまう計算方法を指す。

ある問題について、その問題を解くためのあるアルゴリズムが計算を終えるまでの時間が、問題のサイズ n に対して m (n ) であったとしよう。

• m (n ) = Ω(cⁿ)を満たすc > 1
• m (n ) = O(dⁿ)を満たすd

この2つが存在するとき、このアルゴリズムは指数関数時間のアルゴリズムであるという。

ただし、ΩやOはO記法である。

例

この節の加筆が望まれています。

関連項目

• 多項式時間
• 準指数関数時間
• EXPTIME
• 定数時間