数据库查询是 NP-Hard 问题

作者: , 共 465 字

问题来自美人他爹Wangjianshuo's blog

一个查询的例子: NOT (AND ((C1>5), OR ((C2<6),(C3<>9))))

问题 1 :给出两个这样的查询 Q1 和 Q2 ,如何确定 Q1 的结果是否是 Q2 结果的子集?

上面两篇文章主要是讨论实际工作中怎么解决问题 1。下面从理论上分析一下这个问题。

问题 2 :判断 Q1 查询结果是否为空集。

在问题 1 中让 Q2 查询结果为空集,故问题 1 是比问题 2 更难的一个问题。

论断:问题 2 是NP-hard的。

证明:从 3SAT 问题很容易规约到问题 2。

结论:问题 1 是 NP-Hard 的,除非 NP=P ,不可能有多项式级别的解。也就是理论上而言,解决上面的问题除了枚举没有别的好方法了。

当然以上只是理论,实际应用中,\( 3^n\) 的计算速度和\( 2^n\) 的计算速度还是有很大的区别。如何解决 NP-Hard 问题也是一个被广泛研究的课题,毕竟实际工作中很多问题都是 NP-Hard 的。

Q. E. D.

类似文章:
相似度: 0.308
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
上篇文章扫雷是 NP 完全问题之后,You Xu提到"不光扫雷是 NP 完全问题,空当接龙问题也极有可能是一个 NP 完全问题。目前最好的通用 planner 只能解半副牌"。他说对了,不光扫雷, Windows 自带的游戏都是 NP 完全的。Windows 自带的游戏除了扫雷,还有空当接龙和蜘蛛纸牌。
2014-03-25 更新:我已经将该类修改成函数形式,并增加新功能,参见更新 Excel 的数据库查询函数库
理论计算机(I)课上讲的一个问题,很有意思。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
Excel 多表合并和查询是一个应用很广泛的问题。下面是一个简单的例子,我们需要从两张数据表里,得出每个行业的股票波动率平均值。第一个数据表保存了股票和行业的对应关系,有两列,第一列为股票名,第二列为每只股票对应的行业。第二张表保存了各个股票在各个交易日的收盘价和前收盘价,有四列,第一列是股票名,第二列为交易日,第三列和第四列分别为股票在这个交易日的前收盘价和收盘价。
Game Theory 即博弈论,目前在经济学中运用得最多(纳什更因为他在这上面的工作拿到了诺贝尔经济学奖)。但在最近几年,理论计算机界对它的研究也很热。
Solax那里看到一个伟大的项目——reCAPTCHA
碎碎念 » 谣言
前面 YY 无极限,最后一句最精彩,各位好好体会。