这是系列中的第8篇，我们主要讨论计算中交互作用的用处和IP类问题是什么.
为了回答这些问题，我们首先给交互式证明系统一个简洁的介绍.众所周知，零知识证明在密码协议中十分重要.零知识的概念在这篇介绍中有 [1].这种证明的迷人之处就在于断言的可验证性被证明了.为了解释这个东西，Goldwasser， Micali和Rackoff在经典证明系统上增加两种结构变成了交互式证明系统.第一个结构是随机化(randomisation)，也就是说证明的结果可能是错的，但是这种错误只能以很小的概率出现.第二个结构就是像它名字那样，就是交互性(interaction)，静态证明系统被动态的证明代替，动态证明将于验证程序交互并给出断言是否为真.结合这两种结构的经典证明系统就是一个巨大的复杂类问题---IP.
不严谨的说，一个证明就是一个人能让另一个人相信的方法.这两个人在证明系统中叫prover和verifier.
一个经典的数学证明系统就是固定的一些陈述语句的排列.这些排列被prover写下来，然后verifier一步一步的判断这些陈述语句的正确性.这个过程是没有交互的.
任何证明系统应该有下面的属性:
- 有效性 证明应该是有效率的.
- 稳定性 对于错误的命题，很难有不合法的证明
- 完整性 对任何正确的命题都应该有一个证明
回顾NP复杂类问题被看作是一类语言.它的成员都具有可以轻松检查的证书(注:这里建议读读NP的另一种定义，清晰的解释了这个证书是啥.).因此NP恰好就是一类经典证明的语言.
在一个交互式证明系统里，prover和verifier被允许交互式的交换信息.在引入交互证明的概念之前，我们来给出一个例子来解释交互式证明系统是怎么工作的.
例子:图的同构和图的非同构
两个图G和H被叫做同构的，如果G的节点可以重新排列使得它可以和H节点相同.我们定义下面这类语言:
ISO是NP类的语言.尽管节点的数量可能非常大，但是我们能非常容易的验证这个问题.
然后我们考虑ISO问题的补，即Non-isomorphism问题，就是定义语言:
问题是，使用经典的证明我们如何给verifier证明G和H不是同构的.我们不知道如何提供一个短的证明，多项式时间无法对每个情况进行检查.因为我们不知道如何证明NOISO在NP中.然而在考虑到交互式证明，prover可以说服verifier，这两个图是不同构的(多项式时间内).
prover和verifier都有一对图作为初始输入.verifier随机的选择一个随机比特(bit)和一个排列.然后将应用到得到一个图.(这里意思就是说和同构)verifier发送给prover.然后prover在收到之后，prover发送一比特给verifier.最后verifier接受当且仅当.
在协议背后的观点就是，如果被给的不是同构的，那么prover应该能够确定是来自于或者的.然而，如果输入的两个图是同构的，那么尽管有着无限的计算能力，prover最好的选择就是随机的猜.这种情况下，prover至少1/2的接受.
从上面的例子中，我们总结NOISO不能被verifier用一个古典的证明系统证明.但是它可以被一个交互的证明系统证明.我们能看到交互的力量.
现在我们给出交互式证明系统的定义和IP复杂类的定义.
交互式证明系统:一对交互机被叫做语言的交互式证明系统，如果V是多项式时间的，(P的计算能力是无限的)，和现在的条件满足:
- 完整性:对所有的，
- 稳定性:对所有的，
IP类复杂问题:IP类问题包含所有交互式证明系统能证明的语言.
通过定义，在BPP语言中的所有语言都在IP中.如果我们限制交换的信息的数量为1，那么这就是IP中的NP类问题.实际上，IP是一个很大的类.在1992年，Shamir证明了[3].
额外的，注意到协议prover应该抛出私有的硬币，如果prover被允许访问verifier的随机字符串，就会导致使用共有硬币的交互式证明，这种模型和AM复杂类[4]很像.
[1] http://dl.acm.org/citation.cfm?id=63434
[2] http://www.amazon.co.uk/Introduction-Theory-Computation-Michael-Sipser/dp/0619217642
以上就是本篇文章【第八个知识点：交互式的定义如何帮助计算和IP类问题是什么】的全部内容了，欢迎阅览 ！ 文章地址：http://sicmodule.glev.cn/news/420.html 资讯 企业新闻 行情 企业黄页 同类资讯 首页 网站地图 返回首页 歌乐夫资讯移动站 http://sicmodule.glev.cn/mobile/ , 查看更多