Kontainmen bersama yang paling dikenal untuk / oleh NP dan Parity-P?

18

Parity-P adalah seperangkat bahasa yang dikenali oleh mesin Turing non-deterministik yang hanya dapat membedakan antara jumlah genap atau ganjil dari jalur "penerimaan" (daripada jumlah jalur penerimaan yang nol atau tidak nol). Dengan demikian Parity-P pada dasarnya adalah adik kandung PP kerdil: sementara PP menghitung apakah jumlah jalur penerimaan mesin NP adalah mayoritas atau tidak ( yaitu bit paling signifikan dari jumlah itu), Parity-P menunjukkan bit paling sedikit dari jumlah jalur penerimaan.

Seperti NP, Parity-P mengandung UP (yang berisi P, "mungkin" benar-benar demikian); dan seperti NP, Parity-P terkandung dalam PSPACE.

Pertanyaan. Apa batas atas dan bawah untuk NP dan Parity-P yang paling dikenal?

cc.complexity-theory complexity-classes np Niel de Beaudrap
sumber

Jawaban:

17

Oleh Valiant-Vazirani, NP terkandung dalam BP dot Parity-P (yang jelas mengandung Parity-P). Selain itu, Toda menunjukkan bahwa PH ada di BP dot Parity-P yang ada di P ^ (# P) (yang ada di PSPACE).

Untuk batas bawah, saya pikir kedua kelas berisi kelas yang dikenal sebagai FewP yang berisi UP dan seperti NP tetapi Anda meminta string dalam bahasa paling banyak secara polinomi menerima jalur.

[Perbarui: kesalahan ketik BPP yang diperbaiki, bukan BP]

Manu
sumber
5
Sebuah konsekuensi wajar dari penahanan PH di BPP dot Parity-P, adalah bahwa Parity-P tidak terkandung dalam Hirarki Poli kecuali kalau Hirarki runtuh.
Andy Drucker
4
Ini mengikuti karena, jika Parity-P dalam Sigma_k-P, maka PH berada di BPP dot Sigma_k-P, yang terkandung dalam Pi_ (k + 1) -P. (penahanan terakhir ini mengikuti dari generalisasi 'operator' langsung dari hasil bahwa BPP berada dalam Sigma_2 P berpotongan Pi_2 P.)
Andy Drucker
4
Saya pikir itu dianggap masuk akal bahwa BPP dot Parity-P terkandung dalam P ^ (Parity-P). Jika ini benar, maka PH terkandung dalam P ^ (Paritas), yang terkandung dalam (Parity-P) ^ (Parity-P), yang sebenarnya sama dengan Parity-P. Yang saya tidak yakin adalah apakah ada makalah tentang kekerasan vs keacakan memberikan hipotesis yang menyiratkan BPP dot Parity-P yang terkandung dalam P ^ (Parity-P).
Andy Drucker
4
Akhirnya, Parity-P dibedakan dari NP dan kelas PH lainnya karena diketahui memiliki pengurangan kasus terburuk hingga rata-rata. Artinya, jika Parity-P tidak dalam P, maka itu berisi masalah distribusi yang rata-rata-keras. Lihat Feigenbaum-Fortnow, "Pengunduran diri sendiri dari set lengkap".
Andy Drucker
3
Inilah ide umum: biarkan C menjadi kelas kompleksitas. Bahasa L berada dalam (BPP dot C) jika ada bahasa S dalam C, yang terdiri dari pasangan yang disandikan (x, r), sehingga: -jika x ada di L, maka untuk 2/3 dari semua r, pasangan (x, r) dalam S; -Jika x tidak dalam L, maka untuk 2/3 dari semua r, pasangan (x, r) tidak dalam S. (Secara teknis, panjang r tergantung pada x dan harus paling banyak polinomial di | x |.)
Andy Drucker