Editing EXPTIME (section)

== Relationships to other classes ==
It is known that

{{block indent|[[P (complexity)|P]] ⊆ [[NP (complexity)|NP]] ⊆ [[PSPACE]] ⊆ EXPTIME ⊆ [[NEXPTIME]] ⊆ [[EXPSPACE]]}}

and also, by the [[time hierarchy theorem]] and the [[space hierarchy theorem]], that

{{block indent|P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE}}

In the above expressions, the symbol ⊆ means "is a subset of", and the symbol ⊊ means "is a strict subset of".

so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are. It is also known that if [[P versus NP problem|P = NP]], then EXPTIME {{=}} [[NEXPTIME]], the class of problems solvable in exponential time by a [[nondeterministic Turing machine]].<ref>{{cite book| last1=Papadimitriou | first1=Christos | title = Computational Complexity| publisher = Addison-Wesley| year = 1994| isbn = 0-201-53082-1| authorlink1 = Christos Papadimitriou}} Section 20.1, page 491.</ref> More precisely, [[E (complexity)|E]] ≠ [[NE (complexity)|NE]] if and only if there exist [[sparse language]]s in '''NP''' that are not in '''P'''.<ref>[[Juris Hartmanis]], [[Neil Immerman]], Vivian Sewelson. "Sparse Sets in NP&minus;P: EXPTIME versus NEXPTIME". ''[[Information and Control]]'', volume 65, issue 2/3, pp.158–181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref>

EXPTIME can be reformulated as the space class APSPACE, the set of all problems that can be solved by an [[alternating Turing machine]] in polynomial space. This is one way to see that PSPACE &sube; EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.<ref>{{harvtxt|Papadimitriou|1994|p=495|loc=Section 20.1, Corollary 3}}</ref>