Kelas Kompleksitas Semantik vs. Sintaksis

Dalam bukunya "Kompleksitas Komputasi", Papadimitriou menulis:

Dalam beberapa hal RP adalah jenis kompleksitas yang baru dan tidak biasa. Tidak ada mesin Turing nondeterministik terikat polinomi dapat menjadi dasar mendefinisikan bahasa dalam RP. Agar mesin N mendefinisikan bahasa dalam RP , ia harus memiliki properti luar biasa yang pada semua input ditolak dengan suara bulat , atau diterima oleh mayoritas . Sebagian besar mesin nondeterministic berperilaku dengan cara lain untuk setidaknya beberapa input ... Tidak ada cara mudah untuk mengetahui apakah mesin selalu berhenti dengan output bersertifikat. Kami secara informal menyebut kelas-kelas semacam itu kelas semantik , yang bertentangan dengan kelas sintaksis seperti P dan NP, di mana kita dapat mengetahui dengan segera dengan cek superfisial apakah mesin standar yang sesuai memang mendefinisikan bahasa di kelas.

Beberapa halaman kemudian, ia menunjukkan bahwa:

bahasa L ada dalam kelas PP jika ada mesin Turing yang dibatasi secara polinomi nondeterministik N sehingga, untuk semua input x, jika jika lebih dari setengah perhitungan N pada input x akhirnya menerima. Kami mengatakan bahwa N memutuskan L secara mayoritas .$x \in L$

Pertanyaan 1: Mengapa Papadimitriou menyimpulkan bahwa PP adalah kelas sintaksis, sedangkan definisinya hanya sedikit berbeda dari RP ?

Pertanyaan 2: Apakah menjadi "semantik" untuk kelas kompleksitas sama dengan TIDAK memiliki masalah lengkap, atau kurangnya masalah lengkap dianggap sebagai properti yang kami GUESS dimiliki oleh kelas semantik?

Sunting: Lihat topik terkait Apakah semua kelas kompleksitas memiliki karakterisasi daun bahasa?

RP melibatkan janji, bahwa 0 jalur diterima atau lebih dari setengahnya menerima, apa pun inputnya. Untuk PP, tidak ada janji seperti itu. Jika lebih dari setengah jalan menerima, maka , jika tidak, x ∉ L . (PP dapat didefinisikan sehingga kriteria penerimaan yang ≥ 1 / 2 dan < 1 / 2 masing-masing.)$x \in L$$x \notin L$$\geq 1/2$$< 1/2$

Atau dengan kata lain, jika saya memberi Anda probabilistik TM yang mengklaim itu adalah mesin PP yang memutuskan beberapa bahasa, Anda dapat yakin bahwa itu memutuskan beberapa bahasa. Jelas, bahasa yang diputuskannya adalah bahasa ini: Coba masukan . Lihat apakah lebih dari 1/2 jalur menerima (atau lebih dari 1/2 string acak menyebabkannya menerima). Jika demikian, x ∈ L . Jika tidak, x ∉ L . Jadi kami telah mendefinisikan bahasa menggunakan TM ini.$x$$x \in L$$x \notin L$

Di sisi lain, jika saya memberi Anda TM probabilistik yang mengklaim itu adalah mesin RP yang memutuskan beberapa bahasa, Anda bahkan tidak dapat memastikan bahwa itu memutuskan bahasa apa pun. Masalahnya adalah ketika Anda mengamati hanya beberapa jalur yang menerima, Anda tidak tahu apakah ada di L atau tidak. Jadi jika saya memberi Anda mesin RP, Anda hanya perlu mengambil kata-kata saya untuk itu. Memang, memeriksa apakah mesin ini mendefinisikan suatu bahasa tidak dapat dihitung.$x$$L$

Adapun pertanyaan kedua Anda, untuk kelas sintaksis biasanya ada masalah lengkap yang jelas, yaitu seperti "Mesin yang diberikan M, putuskan apakah ia menerima dalam waktu T pada input x." Jika Anda diberi mesin nondeterministic, masalah ini adalah NP-complete, jika itu PP-machine, maka itu PP-complete, dll. Masalah lengkap yang jelas untuk kelas semantik tidak dapat diputuskan, seperti yang saya sebutkan. Jadi kami tidak mendapatkan masalah lengkap gratis untuk kelas semantik. Tetapi kelas semantik dapat memiliki masalah yang lengkap. Misalnya jika P = BPP (seperti yang diyakini secara luas), maka BPP memiliki karakterisasi sintaksis.

EDIT : Karena ada beberapa diskusi tentang cara mendefinisikan kelas semantik dan sintaksis, saya ingin menunjukkan bahwa Papadimitriou memberikan definisi dalam bukunya ketika berbicara tentang bahasa daun. (Lihat pertanyaan saya tentang bahasa daun untuk beberapa referensi.)

Dia mengatakan bahwa kelas sintaksis adalah kelas yang ada beberapa bahasa yang mendefinisikan kelas menggunakan teknik bahasa daun. Kelas semantik adalah kelas yang mengharuskan semua penokohan seperti itu untuk masalah janji. Ini adalah definisi yang ketat, tetapi hanya berfungsi untuk bahasa yang memiliki karakterisasi bahasa daun.

$PP$$RP$ $PP$$> 1/2$$x$

$P$$NP$$PP$$RP$$RP$$> 1/2$$RP$$Promise-RP$

$P=BPP$$P=BPP$

Jika memang benar bahwa tidak ada daftar mesin yang mudah dapat dihitung (dari jenis apa pun) yang menerima kelas Anda dengan tepat, maka ya, saya tidak berpikir kelas Anda mungkin memiliki bahasa yang lengkap. Tapi itu sepertinya sangat sulit untuk diformalkan dengan benar, apalagi membuktikan.