Kesalahan satu sisi dalam sistem bukti probablistik

10

Dalam kebanyakan sistem bukti probabilistik (teorema PCP, misalnya), probabilitas kesalahan biasanya didefinisikan pada sisi false-positive, yaitu definisi tipikal dapat terlihat seperti: jika maka verifier selalu menerima, tetapi dalam kasus lain kemungkinan penolakan setidaknya 1/2.x∈L

Apakah ada masalah dalam membiarkan kesalahan terjadi di sisi lain? Itu berarti pemverifikasi selalu menolak kapan seharusnya, dan membuat tidak lebih dari kesalahan konstan ketika harus menerima. Kemungkinan lain yang jelas adalah membiarkan kesalahan di kedua sisi. Apakah definisi ini setara dengan yang biasanya diberikan? Atau, mereka berperilaku berbeda? Atau dalam hal ini, apakah ada masalah asli dalam membiarkan kesalahan di sisi lain.?

cc.complexity-theory pcp interactive-proofs Arnab
sumber
Mengapa downvote? Beberapa PCP tidak memiliki kelengkapan yang sempurna. Di sisi lain, ada beberapa pengurangan dengan kesehatan yang sempurna tetapi tidak kelengkapan yang sempurna ("Bit gratis dll.", Bellare + Goldreich + Sudan, hlm. 21, paragraf terakhir).
Yuval Filmus
@Yuval Filmus: Ada banyak versi makalah yang Anda sebutkan. Versi apa yang Anda maksud?
Tsuyoshi Ito
Terima kasih banyak untuk Anda berdua atas jawabannya. Saya kira downvote berasal dari persepsi bahwa itu bukan pertanyaan "penelitian". Memang tidak. Ngomong-ngomong, aku bahkan tidak bisa mengangkat jawaban dengan skor reputasiku, yang bahkan berkurang hari ini :)
Arnab
@TsuyoshiIto Di versi 2, ini ada di bagian bawah halaman 22 (halaman 24 file).
Yuval Filmus
1
Saya tidak punya ide. Saya baru saja googled "kesehatan yang sempurna".
Yuval Filmus

Jawaban:

12

Mengizinkan kesalahan kelengkapan tidak memiliki masalah, dan sering kali dianggap. Berikut ini beberapa petunjuknya .

Di sisi lain, secara umum, menolak kesalahan kesehatan menghilangkan kekuatan model secara signifikan.

Dalam kasus sistem bukti interaktif, menolak kesalahan kesehatan membuat interaksi tidak berguna kecuali untuk komunikasi satu arah dari prover ke verifier; yaitu, IP dengan tingkat kesehatan sempurna sama dengan NP. Ini dapat ditunjukkan dengan mempertimbangkan mesin NP yang menebak bit acak verifier dan transkrip interaksi yang membuat verifier menerima [FGMSZ89].

Dalam kasus sistem probabilistically checkable proof (PCP), alasan yang sama menunjukkan bahwa memerlukan kesehatan yang sempurna membuat keacakan tidak berguna untuk memilih lokasi yang akan ditanyakan. Lebih tepatnya, dapat ditunjukkan bahwa PCP ( r ( n ), q ( n )) dengan kelengkapan c ( n ) dan kesehatan yang sempurna (bahkan dengan permintaan adaptif) sama dengan kelas C dari masalah keputusan A = ( A ya , A no ) yang memiliki bahasa B ⊆ {0,1} * × {0,1} * × {0,1} * dalam P sehingga

  • jika x ∈ A ya , maka Pr y ∈ {0,1} r ( n ) [∃ z ∈ {0,1} q ( n ) sedemikian rupa sehingga ( x , y , z ) ∈ B ] ≥ c ( n ), dan
  • jika x ∈ A tidak , maka ∀ y ∈ {0,1} r ( n ) ∀ z ∈ {0,1} q ( n ) , ( x , y , z ) ∉ B ,

dimana n = | x |. (Perhatikan bahwa dalam definisi kelas C , kasus ya tidak memerlukan seluruh sertifikat untuk dipersiapkan sebelum verifikasi mengambil string acak y , tidak seperti definisi biasa dari sistem PCP. Sertifikat dapat disiapkan setelah mengetahui y , dan hanya bagian yang diminta dari sertifikat yang diperlukan, itulah sebabnya panjang z adalah q ( n ).) Dikombinasikan dengan batas bawah langsung, ini menyiratkan hal berikut:

  • PCP (log, log) dengan tingkat kesehatan sempurna = P.
  • PCP (poli, log) dengan tingkat kesehatan sempurna = RP .
  • PCP (poli, poli) dengan tingkat kesehatan sempurna = NP.

Membandingkan ini dengan teorema PCP PCP (log, O (1)) = NP dan PCP (poli, O (1)) = NEXP, kita dapat melihat bahwa membutuhkan kesehatan yang sempurna memiliki dampak yang sangat besar.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, dan Stathis Zachos. Tentang kelengkapan dan kesehatan dalam sistem bukti interaktif. Dalam Keacakan dan Komputasi , vol. 5 dari Kemajuan dalam Riset Komputasi , hlm. 429-442, 1989. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps

Tsuyoshi Ito
sumber