EXPTIME
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2"p"("n")) の時間で解ける全ての決定問題の集合である。なお、"p"("n") は "n" の多項式関数である。

DTIMEでは次のように表される。

:formula_1

以下の関係が知られている。

:P formula_2 NP formula_2 PSPACE formula_2 EXPTIME formula_2 NEXPTIME formula_2 EXPSPACE

また、時間階層定理と領域階層定理により、次のようになる。

:P formula_7 EXPTIME   かつ NP formula_7 NEXPTIME   かつ   PSPACE formula_7 EXPSPACE

従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P = NP であれば EXPTIME = NEXPTIME となることが分かっている。NEXPTIME は非決定性チューリング機械で指数関数時間で解ける問題のクラスである。

EXPTIME は空間（領域）のクラス APSPACE にも等しい。APSPACE は交替性チューリング機械で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても PSPACE formula_2 EXPTIME が示される。

EXPTIME は時間計算量に関する階層の一部となっている。2-EXPTIME クラスは EXPTIME と似ているが、二重指数時間 formula_11 かかる問題のクラスである。これを一般化していけば様々な時間計算量のクラスが定義される。
Q205084
計算量理論
Concept
Q163310
チューリング機械
Concept
Q269878
O
Concept
Q3262192
決定問題
Concept
Q36161
集合
Concept
Q1155831
DTIME
MISC
Q846354
P
MISC
Q628036
NP
MISC
Q500716
PSPACE
ORG
Q1575791
NEXPTIME
MISC
Q1141985
EXPSPACE
ORG
None
時間階層定理
UNK
None
領域階層定理
UNK
Q1575791
NEXPTIME
MISC
Q1190223
非決定性チューリング機械
Concept
Q11167512
指数関数時間
UNK
Q438833
交替性チューリング機械
Concept
None
2-EXPTIME
UNK
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
Q1276570
EXPTIME
MISC
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-07-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
7
DATE
2020-07-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
7
DATE
2020-07-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
7
DATE
2020-03-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
3
DATE
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1
DATE
2020-03-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
3
DATE
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2011-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
11
DATE
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+11^^http://www.w3.org/2001/XMLSchema#decimal
11
NUMBER
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
part of
subclass of
subclass of