10 NP-Completeness

文本统计：约 2657 个字 • 3 行代码

10.1 相关概念

图灵机

上述内容是从图灵机 - 维基百科，自由的百科全书中摘录下来的

确定性图灵机：对于每一个输入都会执行确定的行为。

非确定性图灵机：理论上存在，但是并没有被设计出来。对于给定的输入可以有多种选择，但是会选择最正确的解决方案。

P类问题 (Polynomial Problem)

指的是在多项式时间范围内能解决的问题。确定性图灵机多项式时间内可解决的问题。

NP类问题 (Non-deterministic Polynomial Problem)

指的是在多项式时间内“可验证”的问题，也就是不能判断这个问题到底有没有解，而是猜出一个解在多项式时间内证明这个解是否正确，即该问题的猜测过程是不确定的，而对其某一个解的验证需要在多项式时间内完成。P问题属于NP问题，但NP问题不一定属于P问题。等价于非确定性图灵机多项式时间内可解决的问题（但是因为非确定性图灵机没有被设计出来，所以我们讨论的都是多项式时间=可验证）

NPC类问题 (NP-Complete Problem)

存在一个NP问题，并且所有的NP问题都可以规约为它。换句话说，只要是解决规约后的问题，那么所有规约之前的问题都可以解决（大范围->小范围），并且针对的不只是一个问题，针对的是一类问题。

两个限制条件：

• 均为NP问题。
• 所有NP问题都能归约到它。

NP-hard类问题

NP-hard问题指的是满足NPC问题的第二个条件但不一定满足第一个条件，也就是说，NP-hard问题的范围要比NP问题范围广，也就是说所有的NP问题都可规约为此问题，但此问题不一定为NP问题。

10.2 一些问题

Halting problem

问题：Is it possible to have your C compiler detect all infinite loops?

解答：不可能，如果存在这样的 infinite loop-checking program halts,那么对于下面这个程序

def g():
    if halts(g):
        loop_forever()

如果函数g是无限循环的，那么halts(g)为No，那么g就不是无限循环的；如果函数g不是无限循环的，那么g又是无限循环的，形成矛盾！所以不存在这样的判断是否无限循环的程序。

Post correspondence problem

波斯特对应问题 - 维基百科，自由的百科全书

Hamiltonian cycle problem (HCP) and Traveling salesman problem (TSP)

Suppose that we already know that the Hamiltonian cycle problem is NP-complete. Prove that the traveling salesman problem is NP-complete as well.

Hamiltonian cycle problem (HCP) ：Given a graph \(G=(V, E)\), is there a simple cycle that visits all vertices?

Traveling salesman problem (TSP) ： Given a complete graph \(G=(V, E)\), with edge costs, and an integer K, is there a simple cycle that visits all vertices and has total cost \(\le\) K?

我们假定我们已经已知HCP是NPC问题，那么我们可以证明TSP也是NPC问题

要证明一个问题是NPC问题可以分为两个步骤：

1. 证明该问题是NP问题
2. 可以通过一个已知的NPC问题进行多项式规约

在这个题目中我们的第二步就可以通过HCP问题进行多项式规约

证明：显然旅行商问题是一个NP问题，因为每个答案可以被多项式验证

为将HCP多项式规约到TSP，我们需要对比 HCP 和 TSP 的差异。

以 HCP 为基础描述 TSP，实际上就是在一张完全图上寻找总长不超过 \(k\) 的哈密顿环路，具体来说：

HCP	TSP
图 \(G(V,E)\)	完全图 \(G'(V',E')\)
无边权	有边权
-	\(\sum v_i \leq k\)

而为了证明 \(\text{HCP} \leq_p \text{TCP}\)，我们设计一个多项式时间的方法 f() 实现 \(G(V,E) \to G'(V',E')\)，具体来说，它做这些事：

1. 连接 \(G\) 中所有没连上的边，使 \(G\) 成为一张无权完全图；
2. 对于无权完全图中的每一条边 \(v^c_i\)，如果在 \(G\) 中也有这条边，那么令它边权为 0，否则令它边权为 1，于是得到有权完全图 \(G'(V',E')\)；

由于完全图的边数为 \(\frac{n(n-1)}{2}\)，所以这个步骤显然是多项式时间的。

接下来，我们发现，原问题为在 \(G\) 上寻找哈密顿环，等价于在 \(G' = f(G)\) 上做 \(k = 0\) 的 \(TSP\)。由此证明 \(\text{HCP} \leq_{p} \text{TSP}\)，即 \(\text{TSP} \in \text{NPH}\)。

综上所述，由于 \(TSP∈NP\) 且 \(TSP∈NPH\)，所以 \(TSP∈NPC\)。

Note

其实证明一个问题是NPC问题，只要先说明它是NP问题，然后再说明它比某个NPC问题难即可

Circuit-SAT

——The first problem that was proven to be NP-complete

问题：Input a boolean expression and ask if it has an assignment to the variables that gives the expression a value of 1.

3-SAT

3-SAT 指的是 Circuit-SAT 问题的一个特例，它对布尔电路，或者说布尔表达式的形式有特殊要求，具体来说，它要求布尔表达式形如：

\[ (x_1 \vee x_2 \vee x_3) \wedge (x_4 \vee x_5 \vee x_6) \wedge \cdots \wedge (x_{n-2} \vee x_{n-1} \vee x_n) \]

变量是否重复、是否取非不是重点，\(x_1\) 可以和 \(x_6\) 是同一个变量，也可以是某个变量的非，重点是这里的三个一组的形式。

Clique problem and Vertex cover problem

Suppose that we already know that the clique problem is NP-complete. Prove that the vertex cover problem is NP-complete as well.

Clique problem: Given an undirected graph \(G = (V, E)\) and an integer K, does \(G\) contain a complete subgraph (clique) of (at least) K vertices?

判断图里面有没有顶点个数为K的完全子图

Vertex cover problem: Given an undirected graph \(G = (V, E)\) and an integer K, does \(G\) contain a subset \(V' \subseteq V\) such that \(|V'|\) is (at most) K and every edge in G has a vertex in \(V'\) (vertex cover)?

判断图里面又没有一个点集至多有K个，并且所有边都至少有一个端点在这个点集内

同样的证明思路，先证明VERTEX-COVER是NP问题，只需要先检测点是不是V的子集然后依次检测每条边即可

其次证明CLIQUE可被多项式规约为VERTEX-COVER

简洁地说就是图的团可等价转换为补图的最大覆盖

10.3 Formal-language Theory

10.3.1 Abstract Problem

An abstract problem Q is a binary relation on a set I of problem instances and a set S of problem solutions. 我们定义一个抽象问题为问题集合到解集的二元关系

以 \(\text{SHORTEST-PATH}\) 为例

\(I=\{<G,u,v>: G=(V,E) \text{ is an undirected graph};u,v\in V\}\)

\(S=\{<u,w_1,w_2,...,w_k,v>:<u,w_1>,...<w_k,v>\in E\}\)

for every \(i\in I\)，\(\text{SHORTEST-PATH}(i)=s\in S\)

我们将最短路径问题由优化问题通过添加一个参数k转化成一个判定问题，也就是判断这两点之间是否存在长度小于k的路径，这时解空间就变得简单了。

此时，相应的 \(I\) 和 \(S\) 就分别是

\(I=\{<G,u,v,k>: G=(V,E)\text{ is an undirected graph};u,v\in V;k\ge0\text{ is\ an\ integer\}}\)

\(S=\{0,1\}\)

for every \(i\in I\)，\(\text{PATH}(i)=1\ or\ 0\)

10.3.2 Formal-language Theory

相关定义

字母表；An alphabet \(Σ\) is a finite set of symbols

语言：A language L over \(Σ\) is any set of strings made up of symbols from \(Σ\)

Denote empty string by \(ε\)

Denote empty language by \(Ø\)

语言的全集；Language of all strings over \(Σ\) is denoted by \(Σ^*\)

语言的补集；The complement of L is denoted by \(Σ^*-L\)

语言的意思就是由字母表组成的字符串，而语言的全集就是能用字母表组成的所有字符串

The concatenation of two languages L1 and L2 is the language \(L = \{ x_1x_2: x_1 ∈ L_1\ \text{and } x_2 ∈ L_2 \}\).

语言的闭包；The closure or Kleene star of a language \(L\) is the language \(L^*= \{ε\} ∪ L ∪ L^2 ∪ L^3 ∪ ···\), where \(L^k\) is the language obtained by concatenating \(L\) to itself k times

关于算法

Algorithm \(A\) accepts a string \(x ∈ \{0, 1\}^*\) if \(A(x) = 1\)，这个 \(x\) 为一个二进制串

Algorithm \(A\) rejects a string \(x\) if \(A(x) = 0\)

A language \(L\) is decided by an algorithm \(A\) if every binary string in \(L\) is accepted by \(A\) and every binary string not in \(L\) is rejected by \(A\)

一个算法对于任意一个在这个语言集合中的实例，都可以输出1，不在这个语言集合中的实例，都可以输出0，我们就说这个语言可以被这个算法判定。（在这套语言系统中，我们的判定性问题，他的定义其实是答案为yes的实例和它的答案所构成的集合，比如哈密尔顿回路问题，我们把所有带有哈密尔顿回路的图以及这个回路作为我们的问题，所有不存在哈密尔顿回路的图都不在这个集合之中）

To accept a language, an algorithm need only worry about strings in \(L\), but to decide a language, it must correctly accept or reject every string in \(\{0, 1\}^*\)

描述P、NP问题

\(P=\{L\subseteq \{0,1\}^*:\text{there exists an algorithm A that decides L in polynomial time }\}\)

回过头来看P类问题，给定一个language，如果一个算法能在多项式时间内判定这个语言，那么我就说这是P类语言或者说是P类问题

A verification algorithm (验证算法) is a two-argument algorithm \(A\), where one argument is an ordinary input string \(x\) and the other is a binary string \(y\) called a certificate.

A two-argument algorithm \(A\) verifies an input string \(x\) if there exists a certificate \(y\) such that \(A(x, y) = 1\)

用形式语言表达是：The language verified by a verification algorithm \(A\) is \(L = \{ x ∈ \{0, 1\}^* : \text{there exists } y ∈ \{0, 1\}^*\text{such\ that } A(x, y)=1\}\)

那么此时NP问题是多项式时间内可验证问题就被表达为下图

一个问题属于NP是否能够推出这个问题的补问题属于NP？

比如：哈密尔顿回路问题，给你一个图问是否存在哈密尔顿回路；补问题是，给你一个图问是否不存在哈密尔顿回路。

如果一类问题的补集是NP类问题，那么我们把这类问题称为co-NP类问题。

P类问题显然属于co-NP类问题

P问题、NP问题和co-NP问题之间的可能的关系（学术界最倾向于右下角的关系）：

co-NP与NPC无交

描述NPC问题

A language \(L_1\) is polynomial-time reducible to a language \(L_2\) ( \(L_1 ≤_P L_2\) ) if there exists a polynomial-time computable function \(f : \{0, 1\}^* → \{0,1\}^*\) such that for all \(x\in \{0, 1\}^*\), \(x \in L_1\) iff \(f (x) \in L_2\).

转换成直白的话就是，语言\(L_1\)与语言\(L_2\)通过多项式形成了一个一一对应

We call the function \(f\) the reduction function, and a polynomial-time algorithm \(F\) that computes \(f\) is called a reduction algorithm

---

A language \(L ⊆ \{0, 1\}^*\) is NP-complete if

1. \(L ∈ NP\), and

2. \(L’ ≤_PL\) for every \(L’ ∈ NP\).

---

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！