标签： 复杂性理论

1. PCP - Probabilistic Checkable Proof
   2008-10-19, 计算机科学 » NP hard, PCP, 高等理论计算机, 复杂性理论

   PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一，它给了NP 问题一个新的刻画，并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。