P=NP?--算法复杂性和NP问题概述

问题和多项式时间

问题

​ 在开始了解P=NP之前需要首先知道“问题”是什么。这里首先对“问题”做一个形式化的定义:抽象问题Q为问题实例集合I和题解S上的一个二元关系。例如，对于排序问题的一个实例是：n个正整数和排列顺序(升序或者降序)，题解则为一个有效的排列。

​ 为了简单期起见,NP完全性理论只关注判定问题,即题解$S={0,1}$的问题，因此这里可以定义判定问题为从问题实例集合到题解$S={0,1}$的一个二元关系，当然也能直接叫函数关系,即$ s = Q(i),s \in {0,1}$ .

编码和多项式复杂度

​ 编码就是对问题规模的一个形式化的定义。定义抽象集合S(问题实例集合就是一个抽象集合)的编码为S到二进制串集合的映射。在定义编码后，我们就可以对任意一个问题实例i做编码得到其编码$e(i)$.编码$e(i)$的长度就是所谓的问题规模。

​ 如果当提供给算法的是编码长度为$n = |e(i)|$的问题实例i时，算法可以在$O(T(n))$时间内产生问题的解，就说该算法在时间$O(T(n))$内解决完了问题i,特别地，如果$T(n) = n^k$，我们就说该问题是多项式时间内可解的。

注：这里确实挺抽象的，但是仔细想想也不难，主要是把各种各样的问题统一编码称二进制串以便计算机进行解决。

举个几个例子(自己的理解不一定对)：

  1. 对于整数排序问题：我们把输入的n个数字每个数都编码为32为的二进制串（即计算机中int型整数），一共有n个整数，因此编码总长度是n*32 = 32n，在分析复杂性时候常熟往往是不重要的，因此可以认为该问题的输入规模就是n
  2. 对于问题有n个输入$a_1,a_2,…a_n$的问题P,存在一个可在$O(a_nn)$时间内解决该问题的算法，但是该算法并不能说是多项式时间内可解的，因为$a_n$不是编码n的一部分，算法的实际运行时间不仅依赖输入规模n，也依赖编码的实际内容$a_n$,因此是假的多项式时间复杂度。

P类问题

​ 在理解完问题后就能知道什么叫P问题了。定义复杂类P为多项式时间内可解的具体判定问题的集合。

说人话就是对于一个(判定)问题，如果存在一个多项时间的算法能够将其解决就称该问题为P类问题。比如常见的数组排序，最短路径等等。

注意P是一个问题集合。

NP类问题

这里没有用形式化表述是因为设计到一些形式语言的知识，懒得深入了。

​ 对于一个问题X以及它的一个解C，如果存在一个多项式时间的算法能够验证C确实是X的一个解，则称此类问题为NP类问题，或者叫NP问题。比如对于问题“给定数组3 1 2 4 5，求它的一个升序排列“，以及这个问题的一个解C = 1 2 3 4 5，这里很容易（可在多项式时间内）验证排列C是原数组的一个升序排列，因此该问题是一个NP类问题。

​ 定理 $P \subseteq NP$，即一个P问题一定是一个NP问题。

​ 这个定理是很显然的，用求解P问题的一个多项式算法来求出问题P的所有解，并把待验证解和解集合比对即可。

NP完全性与NPC问题

规约和NPC

这里首先定义问题X能在多项式时间内规约到问题Y:对于问题X的任意实例x，都能在多项式时间内构造一个问题y的实例使得如果y输出为真时x也输出为真。该规约过程也记为$X \leq _pY $。

这里谈谈对这句话的理解，由于Y是在X的基础上在多项式时间内转化而来的，因此如果能够解决Y那就一定能解决X了(先把问题X转化为Y，再解决Y就能得到X的一个解）,且解决问题Y的算法一定不比问题X简单：

  • 如果Y是P问题，存在一个多项式算法Q，那么解决X的算法就是多项式时间的规约步骤+Q，结果还是多项式算法，因此Q也是P问题。

  • 如果Y不是P问题，那么不存在一个多项式算法Q，但是这里X可能可以不用规约到Y就能有多项式算法，当然也可能没有，因此Q可能是P问题也可能不是。

这就是规约采用$\leq$而不是$=$的原因了。

在前面我们知道NP问题只有多项式时间的验证算法而不一定有解决算法。在知道规约的概念后，我们自然会想到，存不存在一个问题Y，能让所有的NP问题X都规约到Y,然后再把问题Y解决，那么所有的NP问题不就都解决了吗？

巧了，这样的问题还真有，也就是人们常说的NPC问题，也叫NP完全问题，下面给出该问题的标准定义：

对于NP问题Y,如果对于任意的NP问题X，都有$X \leq_p Y$,那么Y被称为NPC问题。

既然满足我们要求的所有问题都能在多项式时间内规约到Y的问题有了，那我们在多项式时间内解决它不就行了吗？只能说还是太天真了。到目前位置，没有人能证明NPC问题能在多项式时间内解决，也没人能证明不能。

定理 对于NPC问题Y，P能在多项式时间内解决当且仅当P=NP

下面给出证明：

  1. <== 如果P=NP,因为Y是NP问题所以Y也是P问题，所以Y能在多项式时间内解决
  2. ==> 如果Y能在多项式时间内解决，所以Y是P问题，所以$NP \subseteq P$，又因为$P \subseteq NP$,所以$P= NP$

这就是所谓的P=NP问题。