标签： NP hard

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