Candidats naturels pour NP-E et E-NP

On sait depuis le début des années 70 que ${\bf NP}$ et ${\bf E}=DTIME(2^{O(n)})$ ne sont pas égaux (car${\bf E}$ n'est pas fermé par des réductions de plusieurs un en temps polynomial, en revanche à ${\bf NP}$ ). Pour autant que je sache, cependant, il est toujours possible de savoir si une classe est un sous-ensemble de l'autre, ou si elles sont incomparables, ce qui signifie que ${\bf NP}-{\bf E}$ et ${\bf E}-{\bf NP}$ sont tous deux non vides.

Question: Quels sont les problèmes (de préférence naturels) qui sont candidats pour être dans ${\bf NP}-{\bf E}$ ou ${\bf E}-{\bf NP}$ , en supposant que l'ensemble respectif n'est pas vide? Je suis intéressé particularité des problèmes naturels au sein de ${\bf NP}$ qui nécessitent probablement un temps exponentiel avec surlinéaire exposant, par exemple, ils sont en ${\bf NP}-{\bf E}$ .

TQBF (True Quantified Boolean Formulas) est en E et ne sera pas en NP à moins que NP = PSPACE.

Une langue en NP-E est plus délicate. Un tel langage serait également en NP-NTIME (n) et nous n'en avons pas de grands exemples. Vous pouvez utiliser une représentation succincte comme

$L = \{ C \ |\ $Le circuit$C$ décrit un graphe$G$ sur$|C|^5$ nœuds où$G$ est tricolore$\}$ .

$L$ est en NP, il est peu probable qu'il soit en$E$ mais pas si naturel.