Masalah alami dalam

Kelas kompleksitas didefinisikan sebagai berikut (dari Wikipedia ):$\textrm{S}_2^\textrm{P}$

Bahasa adalah dalam S P 2 jika ada predikat polinomial-waktu P sedemikian rupa$L$$S_2^P$$P$

• Jika , maka ada y sedemikian rupa sehingga untuk semua z , P ( x , y , z ) = $x \in L$$y$$z$$P(x,y,z)=1$
• Jika , maka ada z sedemikian rupa sehingga untuk semua y , P ( x , y , z ) = $x \notin L$$z$$y$$P(x,y,z)=0$

di mana ukuran dan z harus polinomial dengan ukuran x .$y$$z$$x$

Lihat juga pos Fortnow dan kebun binatang kompleksitas untuk penjelasan dan diskusi yang lebih informal.

Meskipun kelas ini tampaknya wajar, saya tidak dapat menemukan contoh masalah yang ada di karena alasan yang tidak sepele (yaitu, bukan hanya karena NP atau MA atau beberapa kelas yang terkandung dalam S P 2 ). Adakah yang tahu masalah yang cocok dengan deskripsi ini?$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Jika tidak ada yang bisa memikirkan masalah seperti itu, saya tidak akan keberatan dengan masalah yang ada di dalam sub-kelas dari , tetapi tidak mudah untuk menunjukkan ini, sedangkan masalahnya jelas di S P 2 .$\textrm{S}_2^\textrm{P}$$\textrm{S}_2^\textrm{P}$

Bagaimana dengan masalah yang lengkap untuk janji- ?$\mathsf{S_2^p}$

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, dan Chris Umans. Tentang kerumitan game zero-sum ringkas . Kompleksitas Komputasi 17: 353-376, 2008.

Dari abstrak:

Kami membuktikan bahwa mendekati nilai permainan zero-sum ringkas untuk dalam faktor aditif lengkap untuk janji kelas - , versi "janji" dariS p 2 . Sepengetahuan kami, ini adalah masalah alami pertama yang ditunjukkan lengkap untuk kelas ini.$\mathsf{S_2^p}$$\mathsf{S_2^p}$

(Catatan sejarah: tidak terlalu mengejutkan bahwa tidak banyak masalah alam yang diketahui dalam tetapi tidak diketahui berada di subkelasnya M A atau P N P. Jika Anda memeriksa kertas asli Russell - Sundaram dan Canetti (mandiri), sepertinya definisi S p $\mathsf{S_2^p}$$\mathsf{MA}$$\mathsf{P^{NP}}$$\mathsf{S_2^p}$ dibuat lebih atau kurang secara khusus untuk menangkap argumen mereka yang lebih baik dengan menempatkan dalam P H , daripada untuk menangkap sejumlah masalah alami.)$\mathsf{BPP}$$\mathsf{PH}$