0
$\begingroup$

Let $E = DTIME(2^{O(n)})$ and $NE = NTIME(2^{O(n)})$ be the deterministic/nondeterministic complexity classes of problems decidable in exponential time with linear exponent.

There are many examples of problems "underneath" this class, in $P$ and $NP$, and there are many examples of problems "above" this class, in $EXPTIME$ and $NEXPTIME$. But it seems nice examples of problems that belong to $E$ or $NE$ are scarce.

What are some nice (natural, non-artificial) examples of problems in these complexity classes?

Improve this question
$\endgroup$
1
  • $\begingroup$ What about the most natural EXP-complete language $\{\langle M,x,t\rangle|\text{$M$ decides $x$ in $2^t$ time}\}$? $\endgroup$
    – minh quý lê
    Commented Nov 10 at 17:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.