Journal of Frontiers of Computer Science and Technology ›› 2008, Vol. 2 ›› Issue (1): 20-31.

• 综述·探索 • Previous Articles     Next Articles

PCP theorem and its applications to research on non-approximatable problems

XU Daoyun+   

  1. Department of Computer Science, Guizhou University, Guiyang 550025, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20
  • Contact: XU Daoyun

PCP定理及其在不可近似问题研究中的应用

许道云+   

  1. 贵州大学 计算机科学系,贵阳 550025
  • 通讯作者: 许道云

Abstract: The PCP theorem is one of important results in complexity for recent ten years. The paper introduces the evolution from Turing computation model to the Probabilistically Checkable Proofs(PCP), the basic theory of PCP and its principle and approach to non-approximatable problems.

Key words: PCP theorem, approximation algorithm, non-approximatability, NP-hardness

摘要: PCP定理是近十年来计算复杂性领域内的重要成果之一,介绍了从图灵计算模型到概率可验证明(PCP)计算模型的演变过程、PCP系统的基本理论,以及PCP定理应用于不可近似问题研究的基本原理和方法。

关键词: PCP定理, 近似算法, 不可近似性, NP-难