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

计算机科学与探索 ›› 2008, Vol. 2 ›› Issue (1): 20-31.

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

许道云⁺

贵州大学计算机科学系，贵阳 550025

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20
通讯作者: 许道云

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

XU Daoyun⁺

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

摘要/Abstract

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

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

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定理及其在不可近似问题研究中的应用[J]. 计算机科学与探索, 2008, 2(1): 20-31.

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.

[1]	李伟东，李陈筠然，李建平. l_p范数下具有等级约束的负载均衡问题[J]. 计算机科学与探索, 2016, 10(8): 1184-1190.
[2]	孙焕良，富珊珊，刘俊岭，于戈，许鸿斐. 社会网络中弱关系团队形成问题研究[J]. 计算机科学与探索, 2016, 10(6): 773-785.
[3]	许道云，王晓峰. 一个正则NP-完全问题及其不可近似性[J]. 计算机科学与探索, 2013, 7(8): 691-697.
[4]	韩蒙1, 李建中1,2, 邹兆年2. 从不确定图中发现K紧密子图[J]. 计算机科学与探索, 2011, 5(9): 791-803.
[5]	韩蒙, 李建中, 邹兆年. 从不确定图中发现K紧密子图[J]. 计算机科学与探索, 2011, 5(09): 791-803.
[6]	金澈清1+ ,崇志宏2 ,周傲英3 . 一种实时监控最近邻的近似算法[J]. 计算机科学与探索, 2007, 1(2): 146-159.