Print

概率可验证明（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.结论与进一步工作
  • 致谢
  • 参考文献
  • 附录

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/0a9699b72153df538bdaa695.html