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

• 作者: 许道云
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: PCP定理 近似算法 不可近似性 NP-难
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 综述·探索
• 页码范围: 20-31
• 页数: 12页
• 分类号: TP301
• 字数: 11056字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2008.01.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0