NP完全性

关于问题"P=NP?"，如果能找到NP类中这样一类问题，满足NP类中任何问题都比它们“难”，并且若能判定这类问题属于P类，我们就可以给出这一问题的回答。为了给出形式化描述，我们先定义多项式时间的可归约性。

定义. 若存在多项式时间的DTM U使得对任何输入w，U停机时恰好输出\(f(w)\)，则称函数\(f:A^* \to A^*\)为多项式时间可计算函数。
定义. 语言L称为多项式时间可归约到L'，如果存在多项式时间可计算函数f，使得对每一个输入w，\(w\in L \Leftrightarrow f(w)\in L'.\) 此时记作\(L\le_m L'.\)

利用多项式时间可归约性，我们可以得到P类与NP类语言的一些运算性质：
定理1. (1)设\(A\le_m B.\)若\(B\in P\)，则\(A\in P\)；若\(B\in NP\)，则\(A\in NP\).
(2)若\(A\le_m B, B\le_m C.\)则\(A\le_m C.\)

定义. 如果\(B \in NP; \forall A \in NP, A\le_m B.\) 则称语言B是NP完全的。 NP完全的语言类记为NPC.
定理2. 如果存在\(B \in NPC,B\in P.\) 则\(P=NP.\)
定理3. 如果\(B \in NPC , B \le_m C,C\in NP.\) 则\(C\in NPC.\)


下面讨论SAT相关的问题。
定义. (1)文字是指一个布尔变量或布尔变量的非，即\(x,\overline x.\)
(2)子句是有若干个\(\lor\)连接的文字，如\(x_1\lor x_2 \lor \overline{x_3}.\)
(3)合取范式是由若干个\(\land\)连接的子句，又称为cnf公式，如\[(x_1\lor x_2\lor \overline{x_3})\land(x_3 \lor x_4).\] (4)如果每个子句都恰好有3个文字，则称为3cnf公式。

SAT问题就是任给一个cnf，问是否存在一组文字的赋值，使这个公式成真。3SAT问题对应3cnf.

Cook定理. SAT问题是NP完全的。
定理4. \(SAT\le_m 3SAT,\)而3SAT问题是SAT问题的子问题，从而\(3SAT \in NP.\)综合推出3SAT是NP完全的。

一般地，若要证明某个问题是NP完全的，可以先证这个问题属于NP类，再证明SAT或3SAT问题可以多项式时间归约到此问题上。下面给出一些NP完全的例子。

1. 顶点覆盖问题VC
任给一个无向图\(G=(V,E)\)和非负整数k，是否存在顶点数不超过k的顶点覆盖？
要证\(3SAT \le_m VC\)，考虑任一个3cnf \(F = \bigwedge_{1\le j \le m} C_j\)，设它有\(l\)个变量。
我们构造一个图G，使F可满足当且仅当G有一个不超过k的顶点覆盖。
首先，对每个文字x, 我们构造两个点\(x,\overline{x}\)并将它们连接；对于每一个子句中的三个文字，也将它们连起来。于是G的节点数为\(2m+3l\), 令\(k=m+2l.\)
因为团问题和独立集问题和VC都可以互相多项式时间归约，可得推论：团问题和独立集问题都是NP完全的。

2. Hamilton回路问题HM

3. 整数线性规划问题ILP
任给整数矩阵A和m维向量b，\(Ax\ge b , x\ge 0\)是否有整数解？

最后我们讨论NP类的补运算。显然P类在补运算下是封闭的，但NP类却未必。
定义. \(coNP = \{L | \overline L \in NP.\}\)
定义. 如果\(L \in coNP, \forall L' \in coNP, L'\le_m L.\)称L是coNP完全的。
利用多项式时间变换，可以立得如下结论：
定理5. 如果\(L\le_m L',\) 则\( \overline L \le_m \overline{L'}.\)
定理6. 如果存在NP完全的\(L \in coNP,\) 则\(NP = coNP.\)

    所属分类：TCS     发表于2021-12-14