Y a-t-il un langage clairsemé connu pour être en NPI sous l' hypothèse

10

Je me demande de savoir wether il y a la langue rares (même construit par diagolanization retardée) dans NPI sous l'hypothèse que .P≠NP

cc.complexity-theory complexity-classes Ludovic Patey
la source

Réponses:

13

Je ne sais pas si vous posez un problème ouvert ou s'il a déjà été résolu. Pourtant, l'article suivant peut éclairer ce problème:

Kurtz, SA 1985. Ensembles clairsemés dans NP-P: relativisations. SIAM J. Comput. 14, 1 (février 1985), 113-119. DOI = http://dx.doi.org/10.1137/0214008

Fondamentalement, il déclare que, même en supposant P ≠ NP, il existe un oracle par rapport auquel il n'existe aucun ensemble clairsemé dans NP-P.

D'autre part, le papier suivant:

T. Baker, J. Gill et R. Solovay, «Relativisations of the P =? NP Question», SIAM J. Computing (1975), 431-442. DOI = http://dx.doi.org/10.1137/0204037

montre un oracle par rapport auquel des ensembles clairsemés dans NP-P existent.

NPje⊂NP-P

E≠NE

Hartmanis, J., Sewelson, V., et Immerman, N. 1983. Ensembles clairsemés dans NP-P: Exptime versus nexptime. Dans les actes du quinzième symposium annuel de l'ACM sur la théorie de l'informatique STOC '83 . ACM, New York, NY, 382-391. DOI = http://doi.acm.org/10.1145/800061.808769

(Version du journal disponible ici: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )

MS Dousti
la source
6
Pour énoncer HIS correctement: Il existe des ensembles clairsemés dans NP-P ssi E \ neq NE. Ils utilisaient alors une notation différente.
Lance Fortnow
Merci Lance. Je ne le savais pas. Je vais corriger la réponse dans une minute.
MS Dousti