亚瑟梅林协议

Question

我最近了解了 Arthur-Merlin 协议，我们定义了复杂性类别 $上午，MA$.

我们还看到存在一个定理表明 $AMAMAM...AM=AM$, ，但是我们还没有正式定义 $AMAMAMAM...AM$.

我们确实将其作为协议给出了一个简短的定义，但我希望看到一个正式的定义 无协议, ， 就像 $上午$ 和 $MA$ （和 $MAM$)

的定义 $AMA$ 对我来说应该足够了，只是为了了解它应该是什么样子。

谢谢！

Answer 1

$AMA$ 基本上是一个三轮交互式证明系统，其中验证者（Arthur）只被允许向证明者（Merlin）发送随机性。
我还没有看到这样明确的定义，但我认为我们可以将其表述如下。第一轮AM[3]以Merlin发送消息开始 $m_1$ 给亚瑟。第二轮，亚瑟发送随机性 $r$ 给 Merlin，接下来是最后的第三轮，Merlin 发送一条消息 $m_2$. 。然后 Arthur 决定使用确定性多项式时间验证器接受/拒绝 $V$.

我认为我们可以如下定义该类。
定义： $L ∈ AMA$ 是否存在多时间确定性算法 $V$ 这样：

• 如果 $x \in L \;(|x| = n)$ 然后 $\存在 P.Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 ight) \ge 2/3$ 在哪里 $\;m_1 = P(x),\;m_2 = P(x, r)$
• 如果 $x otin L \;(|x| = n)$ 然后 $\forall P.Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 ight) \le 1/3$ 在哪里 $\;m_1 = P(x),\;m_2 = P(x, r)$

注意证明者 $P$ 是一个函数 $P：\{0,1\}^* \右箭头 \{0,1\}^{q(n)}$, ， 在哪里 $q(n)$ 是一个多项式。

看：Arora-Barak 的第 8.1 节的计算复杂性。