PvsNP.md

definition

problem

大千世界,问题千万. 世间的一切都可以是我们的问题:

1. 天上有没有神仙
2. 地下有没有地府
3. 明天会不会下雨
4. 考试会不会及格
5. 那个妹子会不会接受我
6. 这个数组的最大值是不是42
7. 那个数组的从小到大的排序结果是不是1,2,3,4,5

诸如此类的问题我们都可以称之为问题. 可以看出我们的问题都是有一个特定的问法

就是指某个事件/事物是否符合/满足一个特定的预期?

像这样的问题我们称之为决定性问题/是非问题(decisive problem),答案只有两种可能性,要么是真/是/true的,要么是假/非/false的

多项式时间

指时间复杂度用函数表示形如以下公式所表示:

$$an^x + bn^{x-1} + cn ^{x-2}... + z n + C$$

在这里定义

1. $a,b,c,...,z,C, x$都是常数, $x$是指数
2. $n$是自变量,是数据的规模

对于以上定义,如果一个算法的时间复杂度明确到具体的参数 $a,b,c,...,z,C,x$, 只要以这个形式表达出来,那么就可以说这个算法的时间复杂度取最高次项,可以写作 $$O(n^x)$$

对于任意一个算法,只要某个算法A的时间复杂度小于等于这个值,就可以称这个算法A的时间复杂度在多项式时间之内 例如快排$O(nlogn)$, 顶堆取极值$O(1)$, 遍历一个数组$O(n)$,统统都属于多项式时间之内这个定义.

最后我们认为,如果一个操作可以在多项式时间之内完成,我们将认定这个操作是简单的操作.在这里,这个操作可以是任何定义.

complexity class

复杂度分类是特指算法复杂度的分类,大体上分为两大类,一个是$x$,另一个$Nx$. 这里的x代表的是不同的复杂度,N代表的是非确定性, 例如P 和 NP, exp和Nexp, 甚至 fac和Nfac等等

在算法教学中,我们一般都是用P和NP作为举例,其他复杂度其实也是类似,只不过教学过程中不太用得到,因为复杂度实在是太高,人类比较难以想象,很难举出例子.甚至NP的例子在NPC的情况下就已经非常难以理解了,具体NPC是什么我们下面也会讲解.

1. $x$是指在$x$的时间复杂度内存在一个算法能够解决这个问题,具体我们会在下面用P来举例
2. $Nx$是指在$x$的时间复杂度内存在一个算法能够验证这个问题,具体我们也会在下面用NP来举例

下面我们以P作为例子来进行具体的讲解.

P class

polynomial time, 指存在一个算法能在多项式时间之内解决 所谓的解决是指,对于一个问题的任何设置,总能在规定的时间范围内找到答案,在P问题的定义下当然就变成了在多项式时间内找到问题的解.

例题 1

对于一个数组[3,1,2,5], 请问这个数组的最大值是否是$5$?

注意我们的题目全都是是非/决定性问题.
对于这个问题,我们只需要把数组进行遍历,每次记录当前已知的最大值$max$,如果遍历过程中发现当前元素比目前已知的最大值要大则更新当前最大值$max$.
非常容易看出,只需要$O(4)$(4为问题中数组的元素个数)的时间我们就能找到问题的解.对于这个问题,我们发现数组的最大值是$5$,正好符合题目中的预期,因此问题的结果为真/true

我们也可以延伸扩展这个问题到更加通用的一个问题,即: 给定一个长度为n数组A, 请问其中的最大值是否为$x$? 我们可以用同样的算法,对这个通用的问题进行解答,从而获得问题的真假性. 我们发现对于任意一个符合条件的这样的问题,我们都可以在$O(n)$时间内找到问题的解. 因此我们说,这样的问题可以在多项式时间内得到解决,因此这样的问题是属于P类问题.

事实上我们可以直接把这个问题归结为"在数组中找最大值"的问题这样更好理解,但由于要符合问题的通用性,我在这里并没有直接这么说.

例题 2

对于一个连通图$G$,请问他的最小生成树(MST)的总权值是否小于等于$x$?

与上一个不同,这个例题我直接把问题的抽象形式写了出来,这样一是鼓励大家进行抽象思考,第二是图论问题要用文字简洁的写出来还是有点麻烦的,所以就偷了点懒.

对于这个问题来说,我们只需要找到这个$G$的MST, 无论是使用prim还是kruskal算法,然后将MST的权值加起来,和$x$进行比较即可.得到的答案就是我们的最终是非结果.

例如按照prim算法的性能最差为:

O(VlogV + ElogV) = O(ElogV)

可以近似的看成 $n(log n)$, 因此这个问题的求解时间也是在多项式时间之内.故而我们称,求解G内MST权值和的问题也是属于P类的.

有一点要注意,对于P类问题来说,我们的最终解可以是真也可以是假,一切都要根据具体的题目和问题来进行回答.即使在规定时间内只能回答出假,由于这个是题目的条件约束导致的,并不会影响我们对于这个题目时间复杂度的判定标准.

NP class

全称为nondeterministic polynomial time. 具体是指,对于某一个问题,我不知道这个问题能不能在多少时间内解决, 但我知道,如果给我一个答案(certificate/proof),我可以在多项式时间内去验证这个答案的真伪性(true/false).可以注意这个答案的真假性和决定性问题(decisive problem)的真假性并不是完全一致.

• 决定性问题的真假性是指决定性问题本身的假设和设问的结果是否为真
• 验证NP答案的真假性是指将给定的答案(certificate/proof)代入源问题中,如果用源问题的假设我们发现给定的答案可以满足源问题的设问,则认为该答案是真的,否则是假的. 具体我们会在后面给出举例.

例题1

给定一个图G,求图中是否存在一个path,能够形成一个TSP.

为了能找到一个NP问题,我们直接用经典的TSP作为例子.简单说一下什么是TSP. TSP是指在一个图中(我们不知道它的连通性,回环性等等),从某一个点出发,是否存在一条通路p,能够不重复,不遗漏地走过每一个节点,并且最后能够回到一开始的起点.

从这个问题的面书上我们就可以感觉问题的复杂度,这个问题乍一看就让人感觉不是很简单,似乎找不到一个简单的算法能够快速地计算出问题的解.我的意思是指,如果我们遍历所有可能的路径,应该总能找到问题一个结果:

1. 如果遍历所有路径之后依然没有找到符合条件的路径,我们则认为这个图G不存在这样的TSP
2. 如果遍历的过程中我们找到了一条路径,只要有一条路径,我们就判定这个图G存在一个TSP的解

实际上遍历一个无向连通图的时间复杂度为$O(V + E) \leq O(2V)$, ,而这仅仅是最最简单的图的时间复杂度,那么对于有向图,非连通图来说,遍历的时间复杂度则更加诡异. 更不用提这个时间复杂度仅仅是简简单单的的遍历而已,要说组成一个不重复,不遗漏的路径则需要更加高的时间复杂度. 目前科学界对这个问题的时间复杂度定义还没有一个准确的定论,因此解决这个问题似乎成了一个非常复杂的事情

因此,我们很难下定论说可以在多少时间内解决这个问题,更不用提多项式时间了,那么我们可以说这个问题有可能不是P问题. 但是,如果有一个算法之神从天而降,告诉我们某个具体的图G的TSP是这样这样那样那样的,给我们一个答案路径$p$,写在草稿纸上,然后拂袖离去.我们当然可以惊异于这个神奇的天神下凡,也可以把他给我们的答案去验证一下(难道只有理工男才有这样神奇的思维吗?).

我们如获至宝的拿着这个草稿纸,尝试去验证一下天神给我们的答案. 事实上验证这个答案的正确性似乎不是很难, 我们只需要:

1. 确定这个答案$p$的所有点V和边E和我们原题的设定是完全符合的,没有作弊和更改题目的存在
2. 验证这个答案是否是不重复,不遗漏地走过每一个点
3. 最后这个路径会会到起点,形成一个闭合的路径

验证了以上步骤以后如果所有步骤都是真实无疑的,我们可以感谢一下算法之神天神下凡之举,感叹一下大佬果然是大佬.

那么有没有可能大佬给的答案是错误的呢?或者这个大佬根本就是一个装模作样的大佬,他可能是一个平时神神叨叨的脑瘫,看到我们每天琢磨算法心里非常鄙视,因此随便给我们一个答案来恶心我们一下.这个情况当然也是可能的,因此无论是天神下凡还是脑瘫秀智商,我们都要以严谨的态度以符合题目逻辑的方式去验证问题. 如果问题可以在多项式时间完成验证,并证明这个答案是真的,则我们认为这个问题是NP的 另一方面,如果问题尽管在多项式时间可以跑完验证的流程,如果验证出来结果是错的,则我们无法判定该问题是否是NP的,我们需要继续用其他的答案进行同样的验证,直到我们找到一个能验证为真的答案为止. 那么是否存在一些问题,这种问题无论你用什么答案去验证,都无法得到真的回答呢? 当然有可能,我们称这种问题为Yes instance,更数学的定义如下:

定义一个问题 $\phi$是一个题目逻辑,包含了问题的逻辑和设问, 对于这个问题我们有问题的假设$x$和问题的正确解$y$

1. $(\exists y \rightarrow \phi(x, y) = 1)\Rightarrow$ x是问题的$\phi$的一个yes instance
2. $(\forall y \rightarrow \phi(x, y) = 0)\Rightarrow$ x是问题的$\phi$的一个no instance

例题2

给定一个布尔表达式, $x \cap y \cup z$, 当$x,y,z$取什么值的时候使得该布尔表达式为真

可以非常直观的看出, 以上的具体题目非常简单,只需要让z取true的时候,x和y任意取值都能使整个表达式为真. 但事实上如果将表达式泛化后则会得到一个极其复杂的问题:

定义语句, 为若干布尔自变量$X_i$通过$\cup$,$\neg$和()这几个操作符进行计算. 定义表达式,将若干语句通过$\cap$进行合并 给定一个布尔表达式,以及一系列自变量输入参数$X_i$, 如何设置这些布尔自变量才能使得该表达式为真?

事实上我们并没有一个简单的算法来计算出这些输入值,值得该表达式为真.唯一的办法就是遍历所有可能性来尝试所有布尔表达式的组合.因此该计算的算法复杂度为$O(2^n)$

但是,如果有人能给我们一个答案,写明所有的布尔值排布.我们就可以把这些输入值代入到表达式中,能够非常简单的遍历整个表达式并计算出最终结果.整个过程大概就是$O(n)$的复杂度

总结来说,NP类问题就是,在P时间内可以根据给定的答案来验证源问题是否为真的 那一类问题. 需要强调的是NP问题和P问题并不是互斥的,一个问题需要P时间来验证也可以在P时间内得到解决.如果满足后者条件则我们直接称该问题为P问题而不会在说它是NP问题,因此对P问题的优先级会比NP问题更高一点. 同时我们也可以感觉到,如果一个问题是P问题,那么似乎这个问题比那些NP问题是要难一点的,更复杂一点,好像一般都要难解一点.然而我们也并没有证据证明NP问题一定要比P问题难或者一样难,这就引出了一个世纪大难题 $$ P = NP ? $$ 关于这个问题的具体讨论本文不会多说,有兴趣可以查看其它网上资源

Reduction

说完了P和NP那么我们要研究的问题主体就已经讨论完毕了,接下来讨论一个衍生的问题. 在说明具体的定义之前让我们来一起看看一个具体的例子:

1. 在数组[1,3,5,2,4]中最小是为1
2. 在数组[1,3,5,2,4]中,升序排序的结果为[1,2,3,4,5]

第一个问题是在一个数组中找到最小值,第二个问题是对数组排序.显而易见的是,第二个问题要比第一个问题更复杂一点点,因为第一个问题复杂度为$O(n)$而第二个问题是$O(nlogn)$. 而事实上,我们可以通过解决第二个问题来间接解决第一个问题,我们只需要对数组进行排序,自然就能找到数组中的最小值.尽管通过这种方式我们花费了更多时间去解决了一个原本可以更轻松解决的问题,看似是非常愚蠢的行为,但值得一提的是,我们不需要再为第一个问题写一个专用的算法.只需要利用第二个问题的算法,将该算法包装为一个黑盒,通过将对应的输入喂给这个黑盒,并从黑盒中取出对应的结果,并抽取数组的第一个元素就能得到我们第一个问题的答案了.

这就是所谓的泛用化,或者也有翻译称为归约.主要方法为:

1. 有一个目标问题A,这个问题是你想要解决的问题,这个问题的算法/解法未知
2. 已知一个问题B以及这个问题的算法.需要强调的是这个问题比A更加复杂
3. 存在一个简单的方法可以把问题A的输入和输出转化为问题B的输入和输出
4. 通过将问题A的输入转化为问题B的输入,利用问题B的算法得出B的解,最后将这个解转化为问题A的解

通过以上这些方法我们可以合理利用一个已知的,更复杂的问题的算法/解法,通过输入输出的对应映射,和对算法解法的调用,成功解出目标问题的答案. 可以想象目标问题应该是更简单的,而已知的问题往往是更复杂的. 利用这种特性我们就可以通过利用复杂问题B的解法来解答所有的简单问题A.这些简单问题A们需要符合一个条件

这些A们和B的输入输出之间存在简单的映射方式,

$$ B_i = f(A_i), B_o = g(A_o) $$

再次强调一遍,这个映射方式必须是简单的,换言之,必须要在多项式时间之内完成这一转换

值得一提的是,在讨论这一过程的时候我们往往不会在乎复杂问题更消耗时间这一事情,因为我们往往会认为通过优化算法,使得算法更贴近问题的现实才是学习算法分析的意义所在.而在讨论归约这个题目时,我们要暂时将这一执念抛在脑后.我们要解决的是一个更加宏伟的问题,即心安理得的偷懒 将问题的解法泛用化,找到一切问题的根本所在. 听起来有点哲♂学,有点抽象,但还是很有意思的.

说了这么多关于归约/泛化的例子和概念,让我们一起复习一下它的基本需求

1. 存在一个更复杂的问题B的解法
2. 想要解出一个更简单的问题A
3. 简单问题A和复杂问题B之间存在某种输入和输出的的映射关系,这个映射操作可以在多项式时间内完成

只要符合以上三个条件我们就说, A可以归约化为B,B的复杂度至少和A一样高,也有可能比A复杂得多得多 $$A \preccurlyeq_p B$$

那么我们就会开始想象,有没有这样一种问题B,所有的问题(特指P和NP类的问题),都能归约到这个牛逼的究极问题B. 只要我们解出了这个究极问题,我们就能解决世界上的所有decisive problem.

NPC(complete) class

由此我们引出了一个新的复杂度类别NP完全.一个问题要被称为NPC问题需要符合以下几个条件

1. 必须是一个NP问题
2. 必须必所有NP问题都要复杂,难
3. 所以其他问题都能归约成这个问题

NPC问题和NP并没有太大的差别,他依然可以在多项式时间内得到验证,并且很有可能没有一个简单的算法能的他的解. 但这个NPC是如此的泛用,以至于我们可以用这些的问题的算法来通用的解决所有其他的NP问题. 你可能会非常好奇,还有这种好事?那这种问题应该不存在的吧,如果存在的话那这个世界上应该就没有问题了吧?

由于归约的过程是难度增高的过程,因此想要得到一个NPC问题,我们只有两个途径:

1. 将世界上所有的问题都进行归约,到一个终极问题上去
2. 已知一个NPC问题,我们只需要将这个NPC问题归约到另一个问题,那么我们就能找到另一个NPC问题

非常显然的是如果已经有了一个NPC的情况下,再产生一个新的NPC是简单不少的,那么如果没有第一个NPC问题,我们这个逻辑就不可能形成闭环,那么第一个NPC到底存在吗? 其实NPC问题早就已经被证明存在并有了好几个具体的例子.要感谢Levin-cook theorem,使他们两个人的努力让数学和计算机的世界有了第一个NPC问题,从此其他问题都能归约化成这个第一个NPC问题,而这个NPC问题甚至还能继续归约成其他更加复杂的问题.

第一个NPC问题就是著名的Circuit Satisfiability 问题,称为电路问题, 简称CSAT问题或者C问题.总体来说就是给定很多电路门有与,或,非等等.每个电路门有1个或2个输入电线和一个输出电线,通过各种拼贴和组合,组成一个庞大的电路.这个电路必然会有最外面的两排电线,一个是输入线口,我们可以在这里输入电平;一个是输出线口,我们可以在这里接收到整个电路最终的输出电平. 较为具体的定义如下:

定义组件, 为若干或门和非门进行组合.他们的输入线作为输出,他们的输出线作为输出 定义电路板,位若干组件通过与门进行组合.所有的组件通过拼贴搭线组合在一起,最终会形成一个输出电线 给定一个电路板,以及一系列输入电线头, 如何设置电线头的电平可以使得整个电路板最终的那一根输出电线可以输出高电平,或者说输出1

具体的证明过程由于过于复杂在此不会给出,但我们可以大致想象一下,我们的电脑就是用电路组成的,所以能用电路表示出来的问题也一定会被电路解决,而电路逻辑的本质就是与或非门之间的组合.

另外我们也可以发现,这个定义和上面NP问题中的布尔表达式问题几乎一模一样,只是有些语言上的不同. 事实上你的观察确实没错,布尔表达式是一种更高更复杂的电路问题,被称为Satisfiability问题,简称SAT问题或者S问题. 毕竟电路的本质就是与或非逻辑,而布尔逻辑是一种比电门逻辑更纯粹更抽象的存在,更复杂更高级.

最后值得一提的是,所有的NPC问题由于比其他NP问题都要简单,我们也可以称这些问题属于NPH(hard)问题,毕竟他们是更难的嘛

NPH(hard) class

说到最后一种复杂度分类,就是大名鼎鼎的NP难问题了,NPH问题要符合以下条件

1. 比所有NP其他问题都难

对就这一条就已经足够了, 我们知道NPC问题也算是NPH问题,而NPH却不用必须是NP问题,因此那个著名的复杂度分类图中可以看到NPH问题有一部分在NP的圆圈中,而其他大部分都是在NP问题之外的,在此我们也不再详谈, 因为上面提到过的 exp, Nexp, fac, Nfac问题也在这一问题之列.

我们只需要知道,这个问题 非常难就是了

后记

写这篇总结的原因在于,我妹子在学习计算原理相关的知识.这方面的知识其实我在本科只是听过,并没有深入好好的学过,导致现在居然没有办法帮助到她.故而深入查了点资料总结一下,也算是对自己算法分析知识的一个总结. 在花了点时间总结以后发现,其实这些复杂度分类也没有那么复杂,有些概念比较抽象,但其实也不难理解. 几年前在知乎也查过类似的信息,但很多都是片段式的,举一个不太恰当的例子就回答完毕了,个人感觉还是有点片面,故而总结了一下,在这里分享给大家.

如果有不够准确的地方也欢迎提出指正.