Bukti Interaktif untuk HORN-SAT?

10

Adakah cara yang bisa dilakukan oleh seorang pepatah untuk meyakinkan verifier bahwa beberapa ekspresi HORN-SAT memuaskan?

Tentu saja ini mungkin tampak konyol, karena ada algoritma waktu linear untuk HORN-SAT. Di sisi lain, HORN-SAT adalah P-complete, yang berarti tidak memiliki algoritma ruang-log kecuali P = L. Dengan demikian, batasi kemampuan komputasi verifier menjadi L. Sekarang verifier sangat lemah, sehingga masalahnya tidak lagi konyol.

Pelintiran lain dalam hal ini adalah apakah itu bisa menjadi bukti tanpa pengetahuan.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
sumber
1
Dalam kasus non-nol-pengetahuan, saya berpikir bahwa verifikasi naif menggunakan penugasan kebenaran yang memuaskan karena sertifikat hanya membutuhkan ruang log, asalkan input dan sertifikat ditulis pada kaset read-only yang tidak dihitung sebagai ruang.
Tsuyoshi Ito
@ Tsuyoshi: Saya tidak melihat cara melakukan verifikasi naif hanya di ruang log. Jika kita bisa, bukankah itu menunjukkan HORN-SAT dalam NL, dan dengan demikian P-kelengkapannya memberikan P = NL?
Shaun Harker
Tidak. Saya berasumsi sertifikat itu pada kaset hanya baca, yang berbeda dari verifikasi yang dilakukan oleh NL.
Tsuyoshi Ito
@ Tsuyoshi: Ah, jadi Anda dapat membaca sertifikat berkali-kali, sedangkan definisi berbasis sertifikat NL akan memiliki sertifikat yang hanya dapat dibaca sekali.
Shaun Harker

Jawaban:

11

Ini http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf survei yang dilakukan oleh Anne Condon mengandung banyak fakta tentang ruang yang dibatasi sistem bukti interaktif.

Ada beberapa model, dan perbedaan utamanya adalah apakah Anda mengizinkan koin pribadi untuk verifikasi (IP) atau koin publik saja (AM), dan apakah Anda juga membatasi waktu verifikasi menjadi polinomial (tidak tersirat oleh ruang yang terikat sendirian).

Tanpa batasan waktu, jawabannya adalah ya: IP (ruang log) berisi EXP dan AM (ruang log) = P.

Perhatikan bahwa IP (ruang log) kemungkinan besar lebih besar dari IP standar. Di sisi lain IP (ruang log, waktu poli) = IP = PSPACE.

AM (log-space, poly-time) = P karena 'Mendelegasikan Komputasi: Bukti Interaktif untuk Muggle' oleh Goldwasser et al., STOC 2008.

Lebih lanjut, makalah 'Nol pengetahuan dengan pengukur ruang-log' oleh Kilian (FOCS 88) menunjukkan cara mendapatkan sistem bukti-bukti nol-waktu-ruang poly-time untuk semua dalam IP (dengan koin pribadi jelas).

Hartmut Klauck
sumber
1
Saya juga menemukan sebuah makalah berjudul Delegating Computation: Interactive Proofs for Muggle . Apakah Teorema 3 dari karya ini menunjukkan bahwa AM (log-space, poly-time) = P?
Shaun Harker
Ya, mereka memang menunjukkan itu!
Hartmut Klauck