Protocollo Arthur-Merlin

Question

Ho appreso di recente del protocollo di Arthur-Merlin, e abbiamo definito le classi di complessità $ am, mA $ .

Abbiamo anche visto che esiste un teorema affermando che $ amamam ... am= AM $ , tuttavia non abbiamo definito formalmente $ Amamamam ... AM $ .

Abbiamo dato una breve definizione per questo come protocollo, ma vorrei vedere una definizione formale senza protocolli , proprio come $ AM $ e $ mA $ (e $ mam $ )

A Definizione per $ AMA $ Dovrebbe sufficienza per me, solo per ottenere il passo di come dovrebbe guardare.

Grazie!

Answer 1

$ AMA $ è fondamentalmente un sistema di prova interattivo a 3 round in cui il verificatore (Arthur) è permesso solo di inviare casualità al Prover (Merlin).
$ M_1 $ ad Arthur. Nel secondo round, Arthur invia casualità $ R $ a Merlin, che è seguito dal terzo round finale in cui Merlin invia un messaggio $ M_2 $ . Arthur decide quindi di accettare / respingere usando il verificatore polinomiale deterministico $ V $ .

Penso che possiamo definire la classe come segue.
Definizione: $ l ∈ AMA $ Se esiste un algoritmo deterministico poli-tempo $ V $ tale che:

.
• se $ x \ in l \; (| x |= n) $ quindi $ \ esiste P. PR_ {r \ in \ {0,1 \} ^ {p (n)}} \ sinistra (V (x, m_1, r, m_2)= 1 \ destra) \ ge 2/3 $ dove $ \; m_1= P (x), \; m_2= p (x, r) $
• se $ x \ notin l \; (| x |= n) $ quindi $ \ forlt P. PR_ {r \ in \ {0,1 \} ^ {p (n)}} \ \ sinistra (v (x, m_1, r, m_2)= 1 \ destra) \ le 1/3 $ dove $ \; m_1= P (x), \; m_2= p (x, r) $

Nota il prover $ p $ è una funzione $ P: \ {0,1 \} ^ * \ Randera \ {0,1 \} ^ {q (n)} $ , dove $ q (n) $ è un polinomiale.

VEDI: Comptidistia computazionale di Arora-Barak's Section 8.1.