标签: 高等理论计算机

PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了 NP 问题 一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
姚期智教授给清华大学新入学研究生开的一门课,课程内容: