理论计算机科学中最经典的问题

1. 定义

1.1 多项式时间:

在计算复杂度理论中,如果指的是一个问题的计算时间 m(n)m(n) 不大于 nn 的多项式倍数。也就是说:

m(n)=O(nk)m(n) = O(n^k)

(此处 kk 为常量)。则该时间就为多项式时间。

1.2 PP 问题:

  • 能够在多项式时间内解决的问题

例如求一序列最大值,很显然时间复杂度为 O(n)O(n) 。这种问题就是 PP 问题。

1.3 NPNP 问题:

  • 能够在多项式时间内验证的问题

2. P=NP?P = NP?

很显然,所有 PP 问题都是 NPNP 问题,因为能在多项式时间内求解,必然也能验证,只需要和正解比较一下即可。

但是不是所有 NPNP 问题都是 PP 问题呢?

我们把这些问题看做集合,所有 PP 问题都是 NPNP 问题的子集。假设 NPNP 问题也都是 PP 问题,那也就是说 P=NPP=NP。现在所有对于 NPNP 问题的研究都集中于该问题上,即是否有 N=NPN=NP

P=NP?P=NP? 这是目前理论计算机科学领域的一大难题。不过主流学术界均认为 PNPP \neq NP

2.1 假如 P=NPP = NP

假设 P=NPP = NP 被证明,不仅仅是计算机科学,各个科学领域都会迎来翻天覆地的变化。

MD5 算法不再有效,判定一个串的 MD5 是否等于给定值与寻找一个 MD5 等于给定值的串一样轻松。

RSA 加密算法也失去意义,寻找一个质因子和判断整除性也变得一样简单。现有密码学体系彻底崩溃,依赖于伪随机数的算法都不安全。

数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单。

所有可被形式化的科学都将受到不同程度的影响...

3. NPCNPC 问题

3.1 背景

NPCNPC 问题也叫 NPNP-完全 问题,CC 是完全的第一个单词。

为了引入 NPCNPC 问题。我们先引入一个概念——约化(Reducibility,也叫归约)

简单地说,一个问题 AA 可以约化为问题 BB 的含义即是,可以用问题 BB 的解法解决问题 AA,或者说,问题 AA 可以“变成”问题 BB

「问题 AA 可约化为问题 BB」有一个重要的直观意义:BB 的时间复杂度高于或者等于 AA 的时间复杂度。也就是说,问题 AA 不比问题 BB 难。

3.2 NPCNPC

则是否可以找到一个时间复杂度最高,并且能「通吃」所有的 NPNP问题的这样一个超级 NPNP 问题?答案居然是肯定的。

也就是说,存在这样一个 NPNP 问题,所有的 NPNP 问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的 NPNP 问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的 NPCNPC 问题,也就是 NPNP-完全 问题。

人们想表达一个问题不存在多项式的高效算法时应该说它 「属于 NPCNPC 问题」。

3.2 定义

NPCNPC 问题的定义非常简单。同时满足下面两个条件的问题就是 NPCNPC 问题。

  1. 首先,它得是一个 NPNP 问题;
  2. 然后,所有的 NPNP 问题都可以约化到它。

证明一个问题是 NPCNPC 问题也很简单。

  1. 先证明它至少是一个 NPNP 问题。
  2. 再证明其中一个已知的 NPCNPC 问题能约化到它(由约化的传递性,则 NPCNPC 问题定义的第二条也得以满足;至于第一个 NPCNPC 问题是怎么来的,下文将介绍),这样就可以说它是 NPCNPC 问题了。

既然所有的NP问题都能约化成 NPCNPC 问题,那么只要任意一个 NPCNPC 问题找到了一个多项式的算法,那么所有的 NPNP 问题都能用这个算法解决了,NPNP 也就等于 PP 了。因此,给 NPCNPC 找一个多项式算法太不可思议了。

因此,前文才说,「正是 NPCNPC 问题的存在,使人们相信 PNPP \neq NP」。我们可以就此直观地理解,NPCNPC 问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

3.3 逻辑电路问题

逻辑电路问题是指的这样一个问题:给定一个逻辑电路,问是否存在一种输入使输出为 True

逻辑电路是第一个 NPCNPC 问题。其它的 NPCNPC 问题都是由这个问题约化而来的。因此,逻辑电路问题是 NPCNPC 类问题的“鼻祖”。

逻辑电路问题属于 NPCNPC 问题。这是有严格证明的。它显然属于 NPNP 问题,并且可以直接证明所有的 NPNP 问题都可以约化到它(不要以为 NPNP 问题有无穷多个将给证明造成不可逾越的困难)。证明过程相当复杂,其大概意思是说任意一个 NPNP 问题的输入和输出都可以转换成逻辑电路的输入和输出(想想计算机内部也不过是一些 0011 的运算),因此对于一个 NPNP 问题来说,问题转化为了求出满足结果为 True 的一个输入(即一个可行解)。