概率可验证明（PCP）系统研究

论文摘要

计算复杂性是计算机理论中极其重要的一个领域。它不但包含了一个完整独立而且内容丰富的理论，同时也对许多其它相关的计算机和应用数学领域产生了重大影响。1994年，普林斯顿大学的S．Arora，在他的博士论文中，提出了概率可验证明(PEP)系统，得出了NP的新特征，用该方法来自于对交互证明系统这个概念的扩展，使用了线性代数与编码理论等数学证明技巧，解决了许多计算复杂性方面的问题。因此，国内外很多专家，学者均在对它进行研究。在此前提下，本文对PCP进行了研究和整理，同时，对一些测试系统进行化简工作。

论文目录

• 摘要
• ABSTRACT
• 1、引言
• 2、预备知识和简介
• 2.1 概率论基础
• 2.2 纠错码基础
• 2.3 图灵机
• 2.4 概率图灵机
• 3.概率可验证计算模型
• 3.1 （CNF,r-CNF）判定问题
• 3.2 PCP系统的定义
• 3.3 布尔函数算术化与其在有限域上的延伸
• 3.3.1 布尔函数算术化与标准展开
• 3.3.2 布尔函数在有限域上的延伸
• 3.3.3 布尔函数在有限域上延伸的唯一性
• 3.4 NEXPPOLY的PCP特征
• 3.5 多重线性测试系统的构造
• 3.6 和检验系统的构造
• 4.结论与进一步工作
• 致谢
• 参考文献
• 附录