Existe alguma linguagem esparsa conhecida no NPI sob a premissa de

10

Pergunto-me saber meteorológicas existem linguagem escasso (mesmo construído por diagolanization retardado) em NPI sob a suposição de que .P≠NP

cc.complexity-theory complexity-classes Ludovic Patey
fonte

Respostas:

13

Não sei se você está perguntando um problema em aberto ou se ele já foi resolvido. No entanto, o documento a seguir pode esclarecer esse problema:

Kurtz, SA 1985. Conjuntos esparsos em NP-P: relativizações. SIAM J. Comput. 14, 1 (fevereiro de 1985), 113-119. DOI = http://dx.doi.org/10.1137/0214008

Basicamente, afirma que, mesmo assumindo P ≠ NP, existe um oráculo em relação ao qual não existem conjuntos esparsos no NP-P.

Por outro lado, o seguinte artigo:

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

demonstra um oráculo em relação ao qual existem conjuntos esparsos no NP-P.

NPEu⊂NP-P

E≠NE

Hartmanis, J., Sewelson, V. e Immerman, N. 1983. Conjuntos esparsos em NP-P: Exptime versus nexptime. Nos Anais do Décimo Quinto Simpósio Anual da ACM sobre teoria da computação STOC '83 . ACM, Nova Iorque, NY, 382-391. DOI = http://doi.acm.org/10.1145/800061.808769

(Versão do diário disponível aqui: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )

MS Dousti
fonte
6
Para declarar o HIS corretamente: Existem conjuntos esparsos no NP-P, se E \ neq NE. Eles usaram notação diferente na época.
Lance Fortnow
Obrigado Lance. Eu não sabia disso. Corrigirei a resposta em um minuto.
MS Dousti 27/09/10