交互式证明系统

阐述

交互式证明系统由两个部分组成：

验证者 $V: \Sigma^{*} \times \Sigma^{*} \times \Sigma^{*} \longrightarrow \Sigma^{*} \cup\{\text {A}, \text {R}\}$

接收输入、随机性与消息记录，并给出下一则消息 $V\left(w, r, m_{1} \# \cdots \# m_{i}\right)=m_{i+1}$。

证明者 $P: \Sigma^{*} \times \Sigma^{*} \longrightarrow \Sigma^{*}$

接收输入、消息记录，给出下一则消息 $P\left(w, m_{1} \# \cdots \# m_{i}\right)=m_{i+1}$。

交互

给定 $w,r$，我们称 $(V \leftrightarrow P)(w, r)=\mathrm{A}$，如果存在消息 $m_1,\cdots,m_k$ 使得

1. 对所有偶数 $i$ 有 $V\left(w, r, m_{1} \# \cdots \# m_{i}\right)=m_{i+1}$；
2. 对所有奇数 $i$ 有 $P\left(w, m_{1} \# \cdots \# m_{i}\right)=m_{i+1}$；
3. 最后一个消息 $m_k$ 是 accept。

消息的总量不超过 $p(n)$。

IP = PSPACE

交互式证明系统定义了一个集合 IP，$A$ 属于该集合如果存在一个多项式时间可计算函数 $V$ 使得

• 对有些 $P$，$w \in A \text { implies } \operatorname{Pr}[V \leftrightarrow P \text { accepts } w] \geq \frac{2}{3}$
• 对任何 $P$，$w \notin A \text { implies } \operatorname{Pr}[V \leftrightarrow \widetilde{P} \text { accepts } w] \leq \frac{1}{3}$

它与 PSPACE 相等。

实例

• 图同构问题的否定形式 NONISO 属于 IP；
• 可满足性问题的计数形式 #SAT 属于 IP。

性质

相关内容

参考文献