complexity class EXPTIME
E679188
EXPTIME is a computational complexity class consisting of decision problems that can be solved by a deterministic Turing machine in exponential time with respect to the size of the input.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| EXPTIME | 0 |
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
complexity class
ⓘ
time complexity class ⓘ |
| alternativeNotation | DTIME(2^{poly(n)}) ⓘ |
| assumes | deterministic computation model ⓘ |
| believedToBeProperSupersetOf |
NP
ⓘ
P ⓘ PSPACE NERFINISHED ⓘ |
| characterizedBy | deterministic exponential time algorithms ⓘ |
| closedUnder |
complement
ⓘ
intersection ⓘ polynomial-time many-one reductions ⓘ union ⓘ |
| contains |
NP
ⓘ
P ⓘ PSPACE ⓘ |
| containsCompleteProblem |
certain two-player perfect-information games with polynomially bounded length
ⓘ
generalized checkers ⓘ generalized chess on n×n board ⓘ succinct circuit value problem ⓘ word problem for some finitely presented groups ⓘ |
| contrastWith |
EXPSPACE (exponential space)
NERFINISHED
ⓘ
NP (nondeterministic polynomial time) NERFINISHED ⓘ P (polynomial time) NERFINISHED ⓘ |
| definedBy | time-constructible bounds 2^{p(n)} ⓘ |
| definedOver | decision problems ⓘ |
| formalDefinition | set of decision problems solvable in time 2^{p(n)} for some polynomial p ⓘ |
| formalNotation | EXPTIME NERFINISHED ⓘ |
| fullName | exponential time ⓘ |
| generalizationOf | polynomial-time solvable problems ⓘ |
| hasCompleteProblemsUnder | polynomial-time many-one reductions ⓘ |
| hasResource | time ⓘ |
| introducedInField | computational complexity theory ⓘ |
| knownSeparation | P is strictly contained in EXPTIME under standard time hierarchy theorem assumptions ⓘ |
| machineModel | deterministic Turing machine ⓘ |
| notCharacterizedBy | space bounds ⓘ |
| relatedHierarchy | P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE ⓘ |
| relationshipStatusWithNP | NP vs EXPTIME is open ⓘ |
| relationshipStatusWithP | P vs EXPTIME is open ⓘ |
| relationshipStatusWithPSPACE | PSPACE vs EXPTIME is open ⓘ |
| studiedIn | theory of algorithms ⓘ |
| subsetOf | EXPSPACE ⓘ |
| supersetOf |
NP
ⓘ
P ⓘ PSPACE NERFINISHED ⓘ |
| timeBoundType | exponential time ⓘ |
| timeComplexityForm | O(2^{p(n)}) for some polynomial p ⓘ |
| typicalProblemDomain |
generalized board games
ⓘ
succinctly represented state spaces ⓘ |
| typicalRunningTimeForm | 2^{n^k} for some constant k ⓘ |
| upperBoundFor | problems solvable by exhaustive search over exponentially many configurations ⓘ |
| usedFor | classifying intractable decision problems ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.