Lecture 10 | NP Completeness#

概述#

根据问题的难度，由不同的定义划分，问题可以分为：

P 问题(polynomial time)、NP 问题(nondeterministic polynomial time)、NPC 问题(NP complete)、NPH 问题(NP hard)。除此之外 ，我们还需要额外了解不可计算问题(undecidable)。

由于不可计算问题比较特殊，所以我先放在前面介绍。

我们可以用这样一张图来表示其他几个概念的关系：

Source: https://en.wikipedia.org/wiki/NP-hardness

可以粗浅的按照图中的“Complexity”轴来理解其中的转化关系，接下来给出它们的详细定义：

也就是说 \(NPC = NP \cap NPH\)。

课内案例#

接下来的内容都是课件中提到的一些具体问题和案例。

Halting Problem#

停机问题是一个典型的不可计算问题，它指的是，对于任意一个程序，我们无法设计一个算法来判断它是否会在有限时间内停机（即判断程序是否会死循环）。

我们通过反证法可以证明：

假设存在函数 willHalt(func F) 可以判断函数 F 是否会停机，如果会，则返回 true，否则返回 false。那么我们可以构造一个这样的函数 foo()：

void foo() {
    if ( willHalt(foo) ) {
        while (true) {} // Endless loop.
    }
    return;
}

接下来，如果我们想知道 foo() 是否会停机，就会执行 willHalt(foo)。然而在 foo() 内部也有一个 willHalt(foo)，如果它认为 foo() 会停机，则构造一个死循环；而如果它认为 foo() 不会停机，则选择让它立刻停机，于是这里就产生了矛盾。

理解上面这段内容的关键就是，这里虽然不存在事实意义上的“死循环”，但可以理解为这里存在一个逻辑上的递归，而这种“逻辑上的递归”，正是导致停机问题成为一个不可计算问题的原因。

Hamilton Cycle Problem#

哈密顿回路问题是一个 NPC 问题。

Traveling Salesman Problem#

判定版本的 NPC 证明#

现在，假设我们已知 Hamilton Cycle Problem 问题是一个 NPC 问题，尝试通过多项式时间归约🔍的方式来证明 TSP 也是一个 NPC 问题。

首先回顾证明 NPC 的步骤：

1. 判定该问题是一个 NP 问题；
2. 判定一个已知的 NPC 问题可以多项式时间归约🔍为该问题，或者说判定该问题是 NPH 问题；

代入到这个问题中，也就是我们需要证明：

1. TSP 是一个 NP 问题；
2. Hamilton Cycle Problem 可以多项式时间归约🔍为 TSP；

TSP is NPH

要证明 TSP 是一个 NPH 问题，我们可以通过证明 Hamilton Cycle Problem(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')\)；

右图中所有的蓝边边权都为 0，绿边边权都为 1。

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

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

综上所述，由于 \(\text{TSP} \in \text{NP}\) 且 \(\text{TSP} \in \text{NPH}\)，所以 \(\text{TSP} \in \text{NPC}\)。

Circuit-SAT#

Circuit-SAT 又叫 circuit satisfiability problem，它是最早被证明是 NPC 的问题，即通过 NPC 问题的定义证明。

其具体描述如下：

3-SAT#

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

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

A formal-language Framework#

• TODO: Finish this part.

相关概念#

图灵机#

图灵机有一些变体，而我们在这里引入图灵机是为了介绍 P/NP，只介绍确定型图灵机和非确定型图灵机。

图灵机由一个无限长的纸带和一个读写头组成。纸带被划分为一个个格子，每个格子上有一个符号，读写头可以在纸带上移动，读写头可以读取当前格子上的符号，也可以改变当前格子上的符号。图灵机的状态是一个有限集合，每个状态都有一个转移函数，转移函数的输入是当前状态和当前格子上的符号，输出是下一个状态、下一个格子上的符号和读写头的移动方向。

更本质的来说，图灵机是一种计算模型，我们可以用它来表示任何有限逻辑数学过程。确定型图灵机与我们常规理解的计算机逻辑类似，即下一步要做什么可以根据当前状态确定。而非确定型图灵机则类似于能够进行无限并行，并且最终总是选择通向正确答案的方向的那条路（有点类似于它能开平行宇宙，并且总是让你观测到正确的那一个平行宇宙）。

多项式时间归约#

我们引入 P/NP 等这些概念，是为了衡量问题的复杂程度，而如何在具体的“问题”间传递、比较这种“复杂程度”，就是多项式时间归约(polynomial reduce)的目的。

如果我们能在多项式时间的复杂度内，将问题 A 转化为问题 B，则称问题 A 可以多项式时间归约(polynomial reduce)为 B，记为 \(A \leq_{p} B\)，表示 A 不会比 B 难。

而采取数学语言来描述，则是：