TCS:NP-hard

作者: , 共 750 字

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

类似文章:
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了NP 问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
理论计算机(I)课上讲的一个问题,很有意思。
Xie Xie 给我看了一个链接性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
数学 » open问题, 图论
孙博告诉我的,求证
从 hash 函数到王小云的 MD5 破解我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」,最近在这个问题上又有了新的进展。