证明SAT的NP完全性(NP-completeness)

看懂本文需要提前有哪些知识?

  • 知道什么是图灵机,非确定图灵机
  • 知道什么是SAT问题

什么是NP问题?

首先我们要知道,NP一般都是针对决定性问题(Decision problem)的。比如今天我们要讨论的SAT问题,我们要知道一个布尔表达式能不能被满足,只有Yes和No两种情况。NP问题的定义有以下两种:

  • 问题解能在多项式时间内被验证的问题
  • 能被非确定图灵机在多项式时间内解决的问题

很容易证明这两个定义是等价的。由于我们没有详细定义什么是“验证”“解”,在这里不展开详细证明。粗略地说,如果我们有一个多项式时间的确定图灵机验证问题的解,那就可以构造出一个非确定图灵机去“猜”这个解,然后用那个机器去检验猜的对不对。如果我们有一个非确定图灵机解决这个问题,那么对于每一个(可能的)解,它只会有一个分支在跑(验证)这个解。所以我们只需要模拟这个非确定图灵机在确定的一个分支上的行为,就可以得到一个多项式时间的“验证机”。 对于SAT来说,如果有人告诉你一个布尔表达式是可以被满足的,然后他给出了一组解,你很容易能验证这组解是不是能满足这个布尔表达式。但如果有个人告诉你一个布尔表达式是不能被满足的,你就没有办法很容易地验证他说得对不对。如果定义coSAT为所有不能被满足的布尔表达式的集合,那么验证一个布尔表达式在不在coSAT里,这个问题就是coNP(且是coNP-complete)的。 

证明SAT是NP-complete的

以下证明来自于Michael Sipser的《Introduction to the Theory of Computation》。个人认为是相当精彩的证明。所有名词的翻译来源于这本书的中文版或维基百科。定义一个图灵机的格局(configuration)为图灵机当前的纸带上的字符串,图灵机的读写头的位置,以及图灵机当前所处的状态,这三个组成的集合。我们通常用 \(uqv\) 表示这个图灵机处于状态 \(q\) ,纸带上的内容是 \( uv\) ,且读写头处于 \(v\) 的第一个字母。比如, \(1011q_701111\) 代表纸带当前的内容是 \(101101111\),图灵机当前处于状态 \(q_7\) ,且读写头位于第二个0处。 我们现在要证明所有NP问题都能在多项式时间内被转化到SAT问题。显然枚举所有NP问题是不现实的。我们从NP问题的定义出发。假设有一个NP问题,叫它 \(A\) 吧,那么一定有一个非确定图灵机 \(N\) 能在多项式时间内解决\(A\)。假设\(N\)会在 \(n^k\) 步内结束(实际上是 \(n^k-3\) 步,但这种细节没必要太在意)。定义一个图灵机的画面为一个 \(n^k\times n^k\) 的一个表格,每一行都是图灵机 \(N\) 的一个格局,且整个画面是 \(N\) 的一个分支的格局。

图1 画面

如图1。(暂时不要管window是什么)方便起见,我们让每个格局的第一个和最后一个字符都是#。第一行一定是起始格局(即包含其实状态和输入字符串,且读写头在最左端)。我们要求每一行都能从上一行的格局中合法地转移而来(根据转移函数)。如果其中有一行的格局是接受格局(即状态是接受状态 \(q_{accept}\)),那么我们就说这个画面是接受的。 别忘了我们的目标:将问题A转化成SAT问题。也就是说,对于一个 \(N\) 的输入\(w\) ,我们要在多项式时间内构造出来一个布尔表达式 \(\phi\) , \(N\) 能接受 \(w\) 当且仅当 \(\phi\) 能被满足。 我们首先定义 \(\phi\) 中的变量。令 \(C=Q\cup\Gamma\cup\{\#\}\) ,其中 \(Q\) 是 非确定图灵机\(N\) 的状态的集合, \(\Gamma\) 是 \(N\) 的纸带字母表。另外,我们称画面中的每个格子为一个单元,并用 \( cell[i,j]\)  表示第 \(i\) 行第 \(j\) 列的字符,其中 \(cell[i,j]\in C\)。对于第 \(i\) 行第 \(j\) 列的元素每种可能的情况,我们都有一个变量 \(x_{i,j,s}\) 表示它。如果 \(x_{i,j,s}=1\) ,就代表着第 \(i\) 行第 \(j\) 列的字符是 \(s\) ,其中 \(1\le i, j\le n^k, s\in C\) 。由于 \(C\) 的大小是一个常数,所以我们的字符集的大小仍然是在多项式范围内的。 我们将要构造的布尔表达式 \(\phi\) 是由四个小部分组成的, \(\phi=\phi_{cell}\wedge\phi_{start}\wedge\phi_{move}\wedge\phi_{accept}\)。我们将会一一描述每个部分。


\(\phi_{cell}\) 的构造

\(\phi_{cell}\) 保证的是每个单元里有且仅有一个字符。它的构造如下: \[\phi_{cell}=\bigwedge_{1\le i,j\le n^k}\left[ \left(\bigvee_{s\in C}x_{i,j,s}\right)\wedge\left(\bigwedge_{s,t\in C\\s\ne t}(\overline{x_{i,j,s}}\vee \overline{x_{i,j,t}})\right) \right] \] 这个表达式的意思是,对于每个单元,都至少有一个字符 \(s\) 是它的值,且不存在两个字符 \(s\) 和 \(t\) 同时是它的值。这样就保证了每个单元里有且仅有一个值。


\(\phi_{start}\) 的构造

\(\phi_{start}\)  保证了一个画面的第一行一定是起始格局。它的构造如下:\[\begin{align*} \phi_{start}=&x_{1,1,\#}\wedge x_{1,2,q_0}\wedge \\& x_{1,3,w_1}\wedge x_{1,4,w_2}\wedge\dots\wedge x_{1,n+2,w_n}\wedge\\ &x_{1,n+3,\sqcup}\wedge\dots\wedge x_{1,n^k-1,\sqcup}\wedge x_{1,n^k,\#} \end{align*}\]其中 \(w_i\) 即输入的第 \(i\) 个字符。看起来很复杂,其实说的就是第一行必须是起始格局(即纸带上只有输入字符串,后面都是空的,且图灵机处于起始状态,读写头在最开始)。


\(\phi_{accept}\) 的构造

\(\phi_{accept}\) 保证了画面一定是接受的。这一部分是最简单的,因为只要画面里出现了接受状态,就代表这个画面是接受的。所以它的构造如下:\[\phi_{accept}=\bigvee_{1\le i,j\le n^k} x_{i,j,q_{accept}}\]


\(\phi_{move}\) 的构造

\(\phi_{move}\) 的目的是保证画面中的每一行都能从前一行合法地转移来。这里我们要用到图1里提到过的窗口(window)。对于画面中每一个2×3大小地窗口,我们都需要检验它是否合法。合法的意思就是窗口的第一行可以合法地转移到第二行。(书里也没有讲“合法”的详细定义,但这不影响我们的证明。要详细定义“合法”太麻烦了,意义不大) 举个例子:假设a, b, c是纸带字母表中的字符, \(q_1\) 和 \(q_2\) 是 \(N\) 的两个状态。假设 \(N\) 在 \(q_1\) 状态时,读到了字符a,那么它会把a换成b(即写下b),读写头右移,并且仍保持在状态 \(q_1\) ;如果读到了字符b,它有两种选择(非确定地):

  • 写下c,进入状态 $q_2$ ,读写头左移
  • 写下a,进入状态 $q_2$ ,读写头右移

那么图2里的窗口就全都是合法的窗口。

图2 合法的窗口的例子

图3里的都是非法的窗口。

图3 非法的窗口的例子

(关于这些窗口为什么合法或者非法,应该很好懂,所以我这就不做解释了。如果有疑问可以在评论区提问) Claim:如果画面中每个这样的2×3的窗口都是合法的,那么每一行的格局都是从上一行的格局合法转移来的。证明:对于上一行的格局来说,如果一个字符不与状态字符相邻,那它就不应该变。我们考虑当这个字符处在我们2×3的窗口的第一行正中间时,这是它不管怎么变都是不合法的(参考图2(d),图3(a))。这里我们在最开始和最后加的#号就有了作用,因为有了它们才能保证每个字符都可以在窗口正中间。现在我们考虑第一行正中间是一个状态字符的情况。根据转移函数,我们很容易就能判断出一个窗口是否合法(参考图2(b),图3(b)(c)),且只要这个窗口合法,这个格局的转移部分就是合法的。合法的转移部分+其他字符都不变,保证了格局的转移合法。 

 现在我们要构造 \(\phi_{move}\) 。\(\phi_{move}=\bigwedge_{1\le i< n^k,1<j<n^k} (i,j)\ 窗口是合法的。\)其中 \((i,j)\)  窗口代表 \(cell[i,j]\) 处于窗口第一行正中间的那个窗口。我们枚举所有可能的窗口,筛选出其中的所有合法窗口,然后就可以将 \(\phi_{move}\) 写成:\[\bigvee_{a_1,\dots,a_6是合法窗口} (x_{i,j-1, a_1}\wedge x_{i,j, a_2}\wedge x_{i,j+1, a_3}\wedge x_{i+1,j-1, a_4}\wedge x_{i+1,j, a_5}\wedge x_{i+1,j+1, a_6})\]


目前为止,我们已经构造出了 \(\phi\) 。显然 \(\phi\) 是可满足的当且仅当 \(N\) 会接受 \(w\) 。我们现在只需要分析整个过程的复杂度。前面已经提到了,我们字符集的大小是 \(O(n^{2k})\) ,是多项式复杂度的。 \(\phi_{cell}\) 对于每个单元都有一个常数大小的表达式,所以它的大小也是 \(O(n^{2k})\) 。 \(\phi_{start}\) 的大小显然是 \(O(n^k)\) 的。 \(\phi_{move}\) 和 \(\phi_{accept}\) 都针对每个单元有一个常数大小的表达式,所以它们式 \(O(n^{2k})\) 的。每个部分都是多项式复杂度,所以合起来也仍然是多项式复杂度。


后记

到这里我们就完成了SAT的NP完全性的证明。其实定理的证明并不复杂,难点在于 \(\phi_{move}\) 那一部分。如果能耐心看完的话,一定会体验到一种醍醐灌顶般的感觉吧。复杂度理论有时候就是这么美丽。如果发现了什么错误,或者有对哪些部分的用词造句有建议,或者对哪些部分有疑问,都欢迎在评论区指出。既然都看完了,点个赞再走吧~

参考文献

[1] Sipser, Michael. Introduction to the Theory of Computation (3rd edition). 2015.

发表评论

电子邮件地址不会被公开。