Natural candidates for NP-E and E-NP

Question

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}$.

Answer 1

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.