9
$\begingroup$

It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$). As far as I know, however, it is still open whether one class is a subset of the other, or they are incomparable, meaning that ${\bf NP}-{\bf E}$ and ${\bf E}-{\bf NP}$ are both nonempty.

Question: Which are some (preferably natural) problems that are candidates for being in ${\bf NP}-{\bf E}$ or ${\bf E}-{\bf NP}$, assuming the respective set is not empty? I am particularity interested in natural problems within ${\bf NP}$ that likely require exponential time with superlinear exponent, i.e., they are in ${\bf NP}-{\bf E}$.

$\endgroup$
15
$\begingroup$

TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE.

A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of those. You could use a succinct representation like

$ L = \{ C \ |\ $Circuit $C$ describes a graph $G$ on $|C|^5$ nodes where $G$ is 3-colorable$\}$.

$L$ is in NP, unlikely to be in $E$ but not that natural.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.