数据库查询是 NP-Hard 问题

作者: , 共 494 字

问题来自 美人他爹 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.304
很多人一看到 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) 课上讲的一个问题,很有意思。
Solax 那里看到一个伟大的项目 —— reCAPTCHA
碎碎念 » 谣言
前面 YY 无极限,最后一句最精彩,各位好好体会。