Journal of Frontiers of Computer Science and Technology ›› 2008, Vol. 2 ›› Issue (1): 20-31.
• 综述·探索 • Previous Articles Next Articles
XU Daoyun+
Received:
Revised:
Online:
Published:
Contact:
许道云+
通讯作者:
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-难
XU Daoyun+. PCP theorem and its applications to research on non-approximatable problems[J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(1): 20-31.
许道云+ . PCP定理及其在不可近似问题研究中的应用[J]. 计算机科学与探索, 2008, 2(1): 20-31.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://fcst.ceaj.org/EN/
http://fcst.ceaj.org/EN/Y2008/V2/I1/20
HAN Meng1, LI Jianzhong1,2, ZOU Zhaonian2
/D:/magtech/JO/Jwk3_kxyts/WEB-INF/classes/
