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

<p>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 </p>

<p><span class="math-container">$ L = \{ C \ |\ $</span>Circuit <span class="math-container">$C$</span> describes a graph <span class="math-container">$G$</span> on <span class="math-container">$|C|^5$</span> nodes where <span class="math-container">$G$</span> is 3-colorable<span class="math-container">$\}$</span>.</p>

<p><span class="math-container">$L$</span> is in NP, unlikely to be in <span class="math-container">$E$</span> but not that natural. </p>

CC BY-SA 4.0
2019-01-26T12:19:11.073Z
2019-01-26T12:19:11.073Z
Lance Fortnow
<p>It has been known since the early 70's that  <span class="math-container">${\bf NP}$</span> and <span class="math-container">${\bf E}=DTIME(2^{O(n)})$</span> are not equal (because <span class="math-container">${\bf E}$</span> is not closed under polynomial-time many-one reductions, in contrast to <span class="math-container">${\bf NP}$</span>). 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 <span class="math-container">${\bf NP}-{\bf E}$</span> and <span class="math-container">${\bf E}-{\bf NP}$</span> are both nonempty.</p>

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

<cc.complexity-theory><complexity-classes><np-complete>
Natural candidates for NP-E and E-NP
Andras Farago
# Natural candidates for NP-E and E-NP

(Asked by: username_0 on 2019-01-25)

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

**Tags:** cc.complexity-theory, complexity-classes, np-complete

---

## 1 answers

### Answer by username_1 on 2019-01-26. Score: 16 | Accepted answer

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.


---

