标签: NP hard

PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了 NP 问题 一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。