Natürliche Kandidaten für NP-E und E-NP

Es ist seit den frühen 70er Jahren bekannt, dass ${\bf NP}$ und ${\bf E}=DTIME(2^{O(n)})$ nicht gleich sind (weil ${\bf E}$ im Gegensatz zu ${\bf NP}$ nicht unter polynomialen Mehrfachreduktionen geschlossen ist ). . Soweit ich weiß, ist jedoch noch offen, ob eine Klasse eine Teilmenge der anderen ist oder ob sie unvergleichlich sind, was bedeutet, dass ${\bf NP}-{\bf E}$ und ${\bf E}-{\bf NP}$ beide nicht leer sind.

Frage: Welche (vorzugsweise natürlichen) Probleme sind Kandidaten für ${\bf NP}-{\bf E}$ oder ${\bf E}-{\bf NP}$ , vorausgesetzt, die jeweilige Menge ist nicht leer? Ich bin Besonderheit in natürlichen Probleme innerhalb interessiert ${\bf NP}$ , die wahrscheinlich exponentielle Zeit benötigen , mit superlinear Exponenten, dh sie sind in ${\bf NP}-{\bf E}$ .

TQBF (True Quantified Boolean Formulas) ist in E und wird nicht in NP sein, es sei denn, NP = PSPACE.

Eine Sprache in NP-E ist schwieriger. Eine solche Sprache wäre auch in NP-NTIME (n) und wir haben keine großartigen Beispiele dafür. Sie könnten eine prägnante Darstellung wie verwenden

$L = \{ C \ |\ $Schaltung$C$ beschreibt einen Graphen$G$ auf$|C|^5$ Knoten, wobei$G$ dreifarbig ist$\}$ .

$L$$E$