Exponential time

The class of decision problems solvable by a deterministic Turing machine in time $2^{\mathrm{poly}(n)}$, where $\mathrm{poly}(n)$ is some polynomial in the input length.

See the complexity zoo entry here.

Known relationships

• $\mathbf{PSPACE}\subseteq \mathbf{EXP}$: anything computable in polynomial space can be simulated in exponential time.
• $\mathbf{EXP}\ne \mathbf{P}$: this is one of the few known unconditional separations in complexity theory (by the time hierarchy theorem).
• If $\mathbf{PSPACE}=\mathbf{EXP}$, then $\mathbf{PSPACE}⊈P/poly$ — TODO citation.

Known relationships

• $\mathbf{P}\subseteq \mathbf{NP}\subseteq \mathbf{PSPACE}\subseteq \mathbf{EXP}$.

Relevance to cryptography

The security parameter $\lambda$ in cryptographic definitions ensures that breaking a scheme requires super-polynomial (often near-exponential) time. A scheme that is broken in time $T(\lambda )$ is considered secure if $T(\lambda )\ge 2^{{\lambda }^{ϵ}}$ for some $ϵ>0$ (sometimes stated as $T\ge 2^{\Omega (\lambda )}$). Concrete security bounds track where in the exponential regime a reduction places the hardness.