Lec 10: P/NP Problems⚓︎

Introduction⚓︎

对于规模为 \(N\) 的数据，

• 最简单的问题：时间复杂度为 \(O(N)\)
• 最困难的问题：根本没法用渐进符号衡量，这一类问题称为不可判定问题(undecidable problem)

Computational Model⚓︎

Halting Problem⚓︎

不行！下面给出证明：

// When 'code' can terminate in finite time for input 'data'
// the function will return true, otherwise return false
bool halts(code, data);

void CheckIfHalt(f_code) {
    if (halts(f_code, f_code)) {  
        while (true) { /*empty*/ }  // infinite loop
    }
    else {                        
        return;                     // terminate
    }
}

Loop(P) {
    if (P(P) loops)
        print(YES);
    else
        infinite_loop();
}

Turing Machine⚓︎

关于阿兰 · 图灵

图灵机 (Turing machine) 是与 NP 问题密切相关的一种计算理论模型，它用来模拟任何能够被数学家用算术方法来完成的计算（假设这个“数学家”有无穷的时间、精力、纸和笔，并且完全投入于计算工作）。

图灵机的组成部分：

• 无限的内存：1 条一维的纸带，被分为多个单元，每个单元存储一个符号（数据）
• 扫描器(scanner)/ 读写头：一个有限状态控制器，控制头根据当前状态以及控制头指向的符号来决定如何移动（指令）
• 图灵机的状态是一个有限集合，每个状态都有一个转移函数，转移函数的输入是当前状态和当前格子上的符号，输出是下一个状态、下一个格子上的符号和读写头的移动方向

图灵机的运算过程：

• 改变有限控制状态
• 擦除当前被控制头指向的单元上的符号，并写入新的符号
• 移动控制头（向左移 (L)、向右移 (R) 或保持原位 (S)），注意扫描器的每个控制头在每个状态下只能指向一个单元，并且每次最多移动一个单元

图灵机的种类：

• 确定型 (deterministic) 图灵机：它能够在每个阶段执行一条指令，随后根据当前指令的内容来选择下一条要进行的唯一的指令。
• 非确定型 (nondeterministic) 图灵机：它根据一个有限集合来自由选择下一步要执行的指令。并且若执行时存在能够找到解的步骤，那么它一定能够选择得到此解的正确指令。
  • 它可以对所有的可判定问题给出决策，但无法解决不可判定问题。

Definition⚓︎

总结：P、NP、NP 完全、NP 困难问题之间的关系

归约(reduction) 过程的符号化语言表述：给定任何一个实例 \(\alpha \in\) 问题 \(A\)

• 如果我们能够找到一个程序 \(R(\alpha) \rightarrow \beta \in\) 问题 \(B\)，满足 \(T_R(N) = O(N^{k1})\)
• 且能通过另一个程序 \(D(\beta)\) 在 \(O(N^{k2})\) 得到解
• 且对于 \(\beta\) 的解等同于对 \(\alpha\) 的解，那么：

Formal Language⚓︎

形式语言(formal language)：可以被精确的数学或机器处理的公式定义的语言（或可以理解为编码）。

在探讨形式语言时，我们将问题分为两类：抽象问题(abstract probelm) 和具体问题(concrete problem)。

• 抽象问题 \(Q\) 是一个关于集合 \(I\)（表示问题实例(instance)）和集合 \(S\)（表示问题的解(solution)）的一个二元关系。
• 具体问题实际上是对抽象问题的一种编码(encoding)——将 \(I\) 映射到一个位串上（用 \(\{0, 1\}^*\) 表示），\(Q\) 就变成了具体问题

形式语言的正式定义：

• 字母表 \(\Sigma\) 表示一个有限符号集
• 语言\(L\) 表示由 \(\Sigma\) 中的字符构成的字符串集（\(\Sigma\) 的子集）
  • 语言代表的是一个可判定问题
• 记空字符串为 \(\varepsilon\)，空语言为 \(\emptyset\)
• 包含所有字符串的语言记作 \(\Sigma^*\)
• \(L\) 的补(complement) 记作 \(\overline{L} = \Sigma^* - L\)
• \(L_1\) 和 \(L_2\) 的拼接(concatation) 为 \(L = \{x_1x_2: x_1 \in L_1 \wedge x_2 \in L_2\}\)
• \(L\) 的克莱尼闭包 (Kleene closure) 为 \(L^* = \{\varepsilon\} \cup L \cup L^2 \cup L^3 \cup \dots\)，其中 \(L^k\) 表示连续拼接 \(k\) 个 \(L\)

在决策问题中，\(\Sigma = \{0, 1\}\)（即 01 位串）， \(L = \{x \in \Sigma^*: Q(x) = 1\}\)。

P⚓︎

• 若 \(A(x) = 1\)，称算法 \(A\)接受了字符串 \(x \in \{0, 1\}^*\)；若 \(A(x) = 0\)，称算法 \(A\)拒绝了字符串 \(x\)
• 如果 \(L\) 的每一个位串都能够被算法 \(A\) 接受或拒绝，称语言 \(L\) 能够被算法 \(A\)判定

因此P 类问题可以用形式语言表述为：

NP⚓︎

• 验证算法(verification algorithm) 是一个有两个参数的算法，第一个参数是一个输入字符串 \(x\)，另一个参数是一个位串 \(y\)，称为证书(certificate)（其实就是问题的解）
  • 如果对于输入字符串 \(x\)，存在证书 \(y\)，使得 \(A(x, y) = 1\) 成立，则称 \(A\) 能够验证 \(x\)
  • 如果对于 \(L = \{x \in \{0, 1\}^*\}\) 里的每个 \(x\)，存在 \(y \in \{0, 1\}^*\) 使得 \(A(x, y) = 1\) 成立，则称验证算法 \(A\) 能够验证语言 \(L\)

所以，语言 \(L\) 为NP 问题的充要条件为：存在一个多项式复杂度的双参数算法 \(A\) 和一个常数 \(c\)，使得 \(L = \{x \in \{0, 1\}^*: \text{ there exists a certificate }y \text{ with }|y| = O(|x|^c) \text{ such that } A(x, y) = 1\}\)，我们称算法 \(A\) 能够在多项式时间内验证 \(L\) 的解的正确性。

NP Complete⚓︎

假如已知 \(L \in NP\)，那么我们是否能够得出 \(\overline{L} \in NP\) 的结论（这类问题称为co-NP 问题（反 NP 问题））呢？目前有以下四种猜想：

如果存在多项式复杂度的可计算的函数 \(f: \{0, 1\}^* \rightarrow \{0, 1\}^*\)，\(\forall x \in \{0, 1\}^*\)，\(x \in L_1\) 的充要条件为 \(f(x) \in L_2\)，则称语言 \(L_1\) 是可以多项式时间内归约为语言 \(L_2\) 的，记为 \(L_1 \le_P L_2\)（\(L_1\) 的难度不大于 \(L_2\)），称 \(f\) 为归约函数(reduction function)，称计算 \(f\) 的多项式时间算法 \(F\) 为归约算法(reduction algorithm)。

现在可以用形式语言描述NP 完全问题：如果满足下列条件，称语言 \(L \subseteq \{0, 1\}^*\) 为 NP 完全问题：

• \(L \in NP\)，且
• \(\forall L' \in NP, L' \le_P L\)

Examples⚓︎

HCP to TSP⚓︎

证明

• 因为 TSP 的解能够在多项式时间内得到检验（遍历所有的点和边），因此 TSP 是一个 NP 问题
• 左图表示的是图 \(G\)，显然存在一个哈密顿环；右图表示的是图 \(G'\)（在图 \(G\) 基础上添加了成本为 2 的边），它是一张完全图，且满足 \(K = |V|\)，其中 \(|V|\) 为顶点数

• 现在需要证明的是：\(G\) 有一个哈密顿环的充要条件是 \(G'\) 有一个旅行商环，满足总成本为 \(|V|\)
  • 充分性证明：按从左往右的顺序看上面两张图，这个充分条件是自然成立的
  • 必要性证明：按从右往左的顺序看上面两张图，旅行商环显然只经过成本为 1 的边，那么可以直接去掉红色的边得到图 \(G\)，图 \(G\) 便保留了这个旅行商环，即哈密顿环

综上，TSP 也是一个 NP 完全问题。这符合 NP 完全问题的性质：HCP 这个 NP 完全问题能够归约到另一个 NP 完全问题 TSP 上，且任何能够归约到 HCP 的 NP 完全问题，也能归约到 TSP。

CP to VCP⚓︎

SAT⚓︎

懒得写了 ...

• 3-SAT：k 个子句的合取（\(\wedge\)），每个子句是 3 个变量（或其否定）构成的析取（\(\vee\)）。形如：

  \[ (x_1 \vee \neg x_2 \vee x_4) \wedge (x_2 \vee x_3 \vee \neg x_4) \wedge (\neg x_1 \vee \neg x_3 \vee x_4) \]

• 2-SAT：与 3-SAT 类似，唯一区别在于每个子句是 2 个变量的析取。

相关资料：SAT

评论区