Gibt es eine spärliche Sprache im NPI unter der Annahme

10

Ich frage mich , zu wissen , ob es spärliche Sprache (auch durch verzögerte diagolanization gebaut) in NPI unter der Annahme , dass .P≠NP

cc.complexity-theory complexity-classes Ludovic Patey
quelle

Antworten:

13

Ich weiß nicht, ob Sie ein offenes Problem stellen oder ob es bereits gelöst wurde. Das folgende Papier kann jedoch etwas Licht in dieses Problem bringen:

Kurtz, SA 1985. Sparse Sets in NP-P: Relativierungen. SIAM J. Comput. 14, 1 (Februar 1985), 113-119. DOI = http://dx.doi.org/10.1137/0214008

Grundsätzlich heißt es, dass es selbst unter der Annahme von P ≠ NP ein Orakel gibt, zu dem in NP-P keine spärlichen Mengen existieren.

Auf der anderen Seite das folgende Papier:

T. Baker, J. Gill und R. Solovay, "Relativierungen der P =? NP-Frage", SIAM J. Computing (1975), 431-442. DOI = http://dx.doi.org/10.1137/0204037

zeigt ein Orakel, relativ zu dem spärliche Mengen in NP-P existieren.

NPI⊂NP−P

E≠NE

Hartmanis, J., Sewelson, V. und Immerman, N. 1983. Sparse setzt in NP-P: Exptime versus Nexptime. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing STOC '83 . ACM, New York, NY, 382 & ndash; 391. DOI = http://doi.acm.org/10.1145/800061.808769

(Journalversion hier verfügbar: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )

MS Dousti
quelle
6
Um SEIN richtig anzugeben: Es gibt spärliche Mengen in NP-P, wenn E \ neq NE. Sie verwendeten damals eine andere Notation.
Lance Fortnow
Danke Lance. Das wusste ich nicht. Ich werde die Antwort in einer Minute korrigieren.
MS Dousti