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

10

Es ist seit den frühen 70er Jahren bekannt, dass NP und E=DTIME(2O(n)) nicht gleich sind (weil E im Gegensatz zu 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 NPE und ENP beide nicht leer sind.

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

Andras Farago
quelle

Antworten:

15

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 | SchaltungC beschreibt einen GraphenG auf|C|5 Knoten, wobeiG dreifarbig ist} .

LE

Lance Fortnow
quelle