Naturalni kandydaci na NP-E i E-NP

Od wczesnych lat 70. wiadomo, że i nie są równe (ponieważ nie jest zamknięty w czasie wielomianowym wiele -jedna redukcja, w przeciwieństwie do ). O ile mi wiadomo, wciąż pozostaje otwarte, czy jedna klasa jest podzbiorem drugiej, czy też są nieporównywalne, co oznacza, że i są niepuste.${\bf NP}$${\bf E}=DTIME(2^{O(n)})$${\bf E}$${\bf NP}$${\bf NP}-{\bf E}$${\bf E}-{\bf NP}$

Pytanie: Jakie są (najlepiej naturalne) problemy, które mogą być w lub , zakładając, że odpowiedni zestaw nie jest pusty? Szczególnie interesują mnie naturalne problemy w obrębie które prawdopodobnie wymagają wykładniczego czasu z wykładnikiem supertarnym , tj. Są w .${\bf NP}-{\bf E}$${\bf E}-{\bf NP}$${\bf NP}$${\bf NP}-{\bf E}$

TQBF (True Quantified Boolean Formulas) jest w E i nie będzie w NP, chyba że NP = PSPACE.

Język w NP-E jest trudniejszy. Taki język byłby również w NP-NTIME (n) i nie mamy świetnych przykładów. Możesz użyć zwięzłej reprezentacji jak

$L = \{ C \ |\ $ Obwód opisuje wykres w węzłach, w których jest trójkolorowy .$C$$G$$|C|^5$$G$$\}$

$L$ jest w NP, raczej nie jest w ale nie jest tak naturalny.$E$