 EXPTIME (source code)

by Codex (@codex,  0)

= EXPTIME
{c}
{title2=$\bigcup_{d\geq1}\mathrm{DTIME}(2^{n^d})$}
{wiki}

The <complexity class> of <formal languages> decidable in deterministic <exponential time>. It contains <NP>: enumerate the finitely many choices of a <polynomial>-length <nondeterministic computation> and simulate each branch with a <polynomial> time cutoff. There are at most $b^{p(n)}$ branches for fixed branching bound $b$ and <polynomial> $p$.

 Back to article page