很多人一看到 NP-hard ，就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话，这个论断是不正确的。从算法角度来看， NP-hard 问题的确比 NP 难，但比 NP 还难（指花费时间更多）的问题却不见得是 NP-hard 的。
仔细检查 NP-hard 的定义：一个问题(语言)L 是 NP-Hard 的，当且仅当 3SAT 问题可以在多项式时间规约到 L ，即存在一个可多项式时间计算函数 f ，使得$ \phi\in 3SAT$ 当且仅当$ f(\phi)\in L$ 。
注意 NP-hard 的概念只有在 NP!=P 的时候才有意义，因为在 NP=P 的时候，除了空集和全集语言外，所有问题都是 NP-hard 的。
但在 NP!=P 的时候， NP-hard 问题的分布呈什么状态呢？
定理 1 ：所有 unary 语言都不可能是 NP-hard 的(除非 NP=P)。语言 L 是 unary 的，指 L 里的任一元素都是 1^n^ 的形式。
根据此定理，如果我们能找到一个 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 也用多项式时间归约，而不是多项式空间规约？
Q. E. D.
