TCS:NP-hard

作者:

很多人一看到 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.

类似文章:
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了 NP 问题 一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是 NP 完全的 ...
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
数学 » open问题, 图论
孙博告诉我的,求证
从 hash 函数到王小云的 MD5 破解 我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」,最近在这个问题上又有了新的进展。