Czy jest jakiś rzadki język znany z NPI przy założeniu

Zastanawiam wiedzieć pogoda jest rzadki język (nawet skonstruowany przez opóźnionego diagolanization) w NPI przy założeniu, że .$P \neq NP$

Nie wiem, czy pytasz o otwarty problem, czy też został on już rozwiązany. Jednak następujący artykuł może rzucić nieco światła na ten problem:

Kurtz, SA 1985. Rzadkie zbiory w NP-P: relatywizacje. SIAM J. Comput. 14, 1 (luty 1985), 113-119. DOI = http://dx.doi.org/10.1137/0214008

Zasadniczo stwierdza, że ​​nawet przy założeniu P ≠ NP istnieje wyrocznia, względem której nie istnieją żadne rzadkie zbiory w NP-P.

Z drugiej strony następujący papier:

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

pokazuje wyrocznię, względem której istnieją rzadkie zbiory w NP-P.

Ponieważ , dowodzi to, że w każdym razie dowód nie jest relatywizowany.$NPI \subset NP-P$

EDYCJA: Ponadto istnieją rzadkie zestawy w NP-P wtedy i tylko wtedy, gdy :$E \neq NE$

Hartmanis, J., Sewelson, V., i Immerman, N. 1983. Rzadkie zbiory w NP-P: Exptime versus nexptime. W materiałach z piętnastego dorocznego sympozjum ACM na temat teorii obliczeń STOC '83 . ACM, Nowy Jork, NY, 382-391. DOI = http://doi.acm.org/10.1145/800061.808769

(Wersja czasopisma dostępna tutaj: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )