很多人一看到NP-hard，就从字面上理解成为比NP还难的问题。但如果这里的“更难”指得是解决问题所花费时间更长的话，这个论断是不正确的。从算法角度来看，NP-hard问题的确比NP难，但比NP还难（指花费时间更多）的问题却不见得是NP-hard的。

仔细检查NP-hard的定义：一个问题(语言)L是NP-Hard的，当且仅当3SAT问题可以在多项式时间规约到L，即存在一个可多项式时间计算函数f，使得当且仅当。

注意NP-hard的概念只有在NP!=P的时候才有意义，因为在NP=P的时候，除了空集和全集语言外，所有问题都是NP-hard的。

但在NP!=P的时候，NP-hard问题的分布呈什么状态呢？

定理1：所有unary语言都不可能是NP-hard的(除非NP=P)。语言L是unary的，指L里的任一元素都是1ⁿ的形式。

根据此定理，如果我们能找到一个NP-hard的unary的undecidable问题，就证明NP=P了  。

定理2：Turing机停机问题是NP-hard^{(by Dr. Sun)}。

这个定理有点出人意料，但仔细想想也不难证明。而且这个问题不难转成unary的形式，可惜这个转化过程不是多项式时间的，所以转化过后就不一定是NP-hard的了。

思考1：NEXP里有问题不是NP-Hard吗？

思考2：为什么NP-complete用多项式时间规约，PSPACE-complete也用多项式时间归约，而不是多项式空间规约？

来自：TCS：NP-hard

留言

• At 2007.11.29 01:04, mathena said:
  我混乱了 图灵同学的停机问题不是不可判定的么 怎么成了 NP 的了, 能不能给个paper 链接?

  [Reply]
  • At 2007.11.29 10:25, zhiqiang said:
    NP-hard不需要在NP里面。如果还在NP里面的话，那么它就是NP-complete了，这是NP-hard与NP-complete的唯一区别。

    停机问题是NP-hard这个证明不难，你仔细想想就出来了

分类： 算法艺术 设计模式