dalam hal

Sistem bukti probabilistik umumnya disebut sebagai pembatasan , di mana Arthur hanya dapat menggunakan bit acak dan hanya dapat memeriksa bit sertifikat bukti yang dikirim oleh Merlin (lihat, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).M A f ( n ) g ( n $\mathcal{PCP}[f(n),g(n)]$$\mathcal{MA}$$f(n)$$g(n)$

Namun, tahun 1990 Babai, Fortnow, dan Lund membuktikan bahwa , jadi tidak persis pembatasan. Apa parameter ( ) yang ?$\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$$f(n),g(n)$$\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$

Jika Anda ingin menyatakan kembali definisi MA dalam hal PCP, Anda memerlukan parameter lain untuk PCP, yaitu panjang bukti. MA jelas sama dengan PCP dengan keacakan polinomial, kueri polinomial, dan bukti panjang polinomial. Biasanya panjang bukti dalam PCP tidak dibatasi (yaitu, ia hanya dibatasi secara acak oleh keacakan dan pertanyaan), tetapi ini tidak cukup untuk menyatakan kembali definisi MA.

Jika Anda mencari beberapa karakterisasi dari bentuk MA = PCP ( q ( n ), r ( n )), yang bukan hanya penyajian ulang definisi MA, maka saya tidak berpikir bahwa karakterisasi seperti itu diketahui.

$E = DTIME(2^{O(n)})$$MA$$MA = NP$$BPP = P$$MA$$BPP$

$MA$$NP$ . Kompleksitas masyarakat tampaknya sangat percaya bahwa asumsi kekerasan juga benar.

$AM$ .

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Sudan-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Tsuyoshi Ito menjawab pertanyaan itu secara literal, tetapi saya ingin berkomentar tentang semantik MA dan PCP dan bagaimana mereka berbeda.

MA adalah versi probabilistik dari NP, yaitu, verifier juga dapat menggunakan bit acak poli-banyak.

Dalam PCP kita dapat merujuk pada "keacakan" dari verifier, tetapi biasanya keacakan adalah logaritmik dalam waktu berjalan dari verifier, yaitu, verifier bisa mencoba semua string acak yang mungkin dengan sendirinya. Dengan kata lain, "keacakan" ini tidak membeli verifier daya komputasi apa pun, tidak seperti halnya MA.

[Jadi untuk apa "keacakan" ini bagus? Maksud PCP adalah bahwa untuk verifikasi probabilistik satu tes - dengan jumlah kueri yang konstan ke proof - cukup]

Tambahan (mengikuti komentar Tsuyoshi): Dalam PCP karakterisasi NP waktu berjalan verifier dapat dibuat poly-logaritmik, dan, sama, dalam karakterisasi NEXP waktu berjalan verifier adalah polinomial. Meskipun demikian, keacakan dalam konstruksi PCP biasanya hanya digunakan untuk mengambil tes (dalam penokohan NP, dari banyak tes, dan dalam penokohan NEXP, dari banyak secara eksponensial) dan tidak untuk membantu dengan perhitungan. Selain itu, dalam MA, buktinya adalah ukuran polinomial, sedangkan dalam penokohan NEXP, buktinya adalah ukuran eksponensial.