avatar

目录
P、NP与NPC问题的一些思考

P、NP与NPC问题的一些思考

随便说点


好久没写文章了,眼看今年就快过去一半了。
上次发的博客还是凑数的课程实验报告,笑。
今年上半年因为疫情原因,在家呆了好几个月,这学期学校也不准备开学了。
在学校,尤其是机房、教学楼和图书馆,有学习的氛围,周围的人都在学习,你会不由自主地也沉迷学习中。
然而在家就不一样了,效率完全看个人自控能力,像我这种控制不住就刷上b站知乎了的,这个学期的学习质量堪忧。唯一有点长处的是,这学期认真的记了笔记,放在了语雀上。
以后笔记都在语雀上了,服务器上的笔记网站就要关掉了。
服务器的乐趣就是折腾,我也折腾过不少,现在看来服务器对我还不是刚需。所以今年到期后可能就不再租了,同时博客应该会挂在 coding 或者 github pages 上,访问速度可能会有所下降,不过影响不大,反正大部分访问量都是我自己。


跑题了,拐回来。
我为什么会选择写 P、NP、NPC 问题呢?
因为最近算法课学到了这里,而且这里有一些「未解之谜」,最重要的是,我连着好长时间搞不懂其中的一些问题,经过了长时间讨论分析,最终有点领悟,下面就记录一下我的理解吧。

三种问题的定义

摘自我自己的笔记


P 问题:
对于一个问题,如果存在解决问题的多项式时间代价的算法,那么该问题称为 P 问题。

NP 问题:
如果一个问题的解在多项式时间内可以验证,则称为 NP 问题。可验证的意思是:非确定性地猜测该问题的任意一个解,在多项式时间内能够检测这个解是不是该问题的解。

NP 难问题:
如果对于任意的 NP 问题 Q,Q 都能多项式时间归约到问题 P,则称 P 为 NP 难问题。

NPC 问题:
一个问题既是 NP 问题,又是 NP 难问题,则它被称为 NP 完全问题。

我遇到的问题

问题 1:归约的方向与 NPC 问题的证明


我一直感觉归约的方向有点反直觉。
或者说,我是因为看了教材上给的例子之后才觉得反直觉。


是这样一个例子(简化说明):
划分问题:一个特殊问题
背包问题:一个一般问题
划分问题是背包问题的一个特例(或者说,把背包问题的某些参数确定后,就变成了划分问题)。
已知划分问题是 NPC 问题,证明背包问题也是 NPC 问题。


要证明一个问题 B 是 NPC 问题,做法就是:

  • 证明问题 B 是一个 NP 问题。
    • 按照定义证明即可
  • 证明一个 NPC 问题 A 能够归约到问题 B(问题 A 的难度小于等于问题 B)


教材上说,把背包问题的某些参数确定后,就变成了划分问题,由此得到了「划分问题到背包问题的一个归约」。

看到这里我就有点懵了,我好像看不懂这中间的关系了,具体理清思路后是这样的:
1、A 问题归约到 B 问题,说明 A 问题的难度不高于 B 问题。
2、特殊问题比一般问题简单,所以特殊问题可以归约到一般问题。
3、这个问题里的归约是什么:是一般问题特殊化的过程。

我之前搞不懂,为什么「一般问题的特殊化」是一个「从特殊问题到一般问题的归约」?一直觉得这很反直觉,很矛盾。
后来才理解到,一般问题的特殊化的实质是:构造了一个从特殊问题的参数到一般问题参数的映射,这个映射正是从特殊到一般进行归约所需要的。

最后。
三色问题是四色问题的特例吗?是的。
所以三色问题其实比四色问题简单?对。
如何把三色问题归约到四色问题?把四色问题特殊化为三色问题即可。

问题 2:伪最大团与最大团问题的区别


伪最大团问题:
输入是图 G,有一个常数 k,问图 G 中是否存在大小为 k 的团?
最大团问题:
输入是图 G 和参数 k,问图 G 中是否存在大小为 k 的团?

这两个问题的区别在于,前者的 k 是常数,后者是参数(输入、变量)。
结论告诉我:
1、伪最大团问题是具有多项式时间的解法,因此是 P 问题。
2、最大团问题,暂时没有人找到多项式时间算法,所以只是 NP 问题。

我使用暴力算法: n 个顶点中任选 k 个顶点,并遍历这 k 个顶点可能形成的所有边,总的时间复杂度是 $C(n,k)*\frac{k(k-1)}{2}$。

就是这个式子让我疑惑了。
我一看,左边组合数,分解后是阶乘,多项式,右边也是多项式。
诶?这不就是多项式时间吗?

不仅这两个问题的解相同,我又看到了书上的定理「最大团优化问题在多项式时间可解,当且仅当最大团判定问题在多项式时间可解」,我居然证明出了这个被称为 NPC 问题的最大团优化问题是一个 P 问题?!

理性让我知道自己肯定错了,这么简单的步骤还想破解世界难题?
终于在与同学的一番讨论后我才明白错误的地方:
阶乘!
我把 O(n!) 当成了多项式时间了!

而后再看暴力算法时间复杂度的式子,左边组合数分解后是阶乘除以阶乘,化简得到的是 n^k。
这个式子,对于伪最大团问题来说,k 是常数,所以是多项式时间;但对于最大团问题来说,k 是输入,它的规模是 O(n),所以这个式子其实是 O(n^n),不是多项式时间。

由此这个问题的疑惑变解开了。

由此引出下一个问题:

问题 3:伪多项式时间


有些问题的输入很特殊,你能很明确的确定输入的规模:n 个顶点,n 个数字
之类的。对于这些问题,多项式时间复杂度很好确定。
但对于那些多个输入的问题,或者说输入是一张图,信息很多,变量也很多,那你如何确定一个关于这些变量的式子是不是多项式时间呢?
比如,输入有 n、k,我给的式子是 O(nk)、O(n^k)、O(k^2+n^2)等等,由于第二个问题已经讨论过,所以这几个还是比较好回答的。
但如果是更复杂的输入,似乎教材中并未给出清晰明确的「多项式时间」的定义。

由此引出一个概念:
伪多项式时间。

如果一个问题的 input size(输入规模或输入大小)为 x,某个解决这个问题的算法的最坏时间复杂度为O(x^k),其中 x^k 表示 x 的 k 次方,此处 k 为已知常数,那么这个算法可以成为多项式时间算法。


什么是 input size?
这个问题所有输入用二进制表示下的位数。


经典的伪多项式时间的问题:背包问题、素数判定问题。

知乎上看到这样一个解释:
算法的时间复杂度是输入数据的多项式表达,但却是输入数据长度的指数时间表达。


举个例子,
一问题的输入是一个整数 n,这个整数 n 的大小没有限制,也就是说可能不只是32位、64位等。
解决这个问题的算法的时间复杂度假设为 O(n^3)。
这个问题的输入规模 x = logn(即 n 对应于二进制下的 bit 位数)。
由此得到时间复杂度为 O(2^{3x}),这是一个指数型的代价,则该算法的代价实际上伪多项式时间。


而对比数组排序问题,每个数都是整数,
每次增加一个数,只增加 32 比特,所以原输入规模 x = 32n,
这个问题的算法就是多项式时间的。


分析出来的区别:数据规模。

打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论