Apakah ada bahasa yang jarang dikenal dalam NPI di bawah asumsi ?

10

Saya ingin tahu apakah ada bahasa yang jarang (bahkan dibangun oleh diagolanisasi tertunda) di NPI dengan asumsi bahwa .P≠NP

cc.complexity-theory complexity-classes Ludovic Patey
sumber

Jawaban:

13

Saya tidak tahu apakah Anda menanyakan masalah terbuka, atau apakah sudah diselesaikan. Namun makalah berikut dapat menjelaskan masalah ini:

Kurtz, SA 1985. Set jarang di NP-P: relativizations. SIAM J. Comput. 14, 1 (Februari 1985), 113-119. DOI = http://dx.doi.org/10.1137/0214008

Pada dasarnya, ini menyatakan bahwa, bahkan dengan asumsi P ≠ NP, ada oracle relatif yang tidak ada set jarang di NP-P ada.

Di sisi lain, makalah berikut:

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

menunjukkan relatif oracle yang set jarang di NP-P ada.

Karena , ini membuktikan bahwa, bagaimanapun, buktinya tidak merelatifikasi.NPsaya⊂NP-P

EDIT: Selain itu, ada set jarang di NP-P jika dan hanya jika :E≠NE

Hartmanis, J., Sewelson, V., dan Immerman, N. 1983. Jarang diatur dalam NP-P: Exptime versus nexptime. Dalam Prosiding Simposium ACM Tahunan Kelimabelas tentang teori Komputasi STOC '83 . ACM, New York, NY, 382-391. DOI = http://doi.acm.org/10.1145/800061.808769

(Versi jurnal tersedia di sini: http://dx.doi.org/10.1016/S0019-9958(85)80004-8 )

MS Dousti
sumber
6
Untuk menyatakan HIS dengan benar: Ada set yang jarang di NP-P iff E \ neq NE. Mereka menggunakan notasi yang berbeda saat itu.
Lance Fortnow
Lance terima kasih. Saya tidak tahu itu. Saya akan memperbaiki jawabannya sebentar lagi.
MS Dousti