计算能力与计算效率

发表于 分类于 阅读次数：

计算能力与计算效率

引入

一个计算模型的计算能力是用它可计算的问题类的大小来刻画的。目前人类尚无找到其它的计算模型，其可计算的问题类超过图灵机的计算能力。

计算效率用算法的时间需求（或空间需求）来刻画。即时空复杂度。

计算复杂性

计算复杂性研究算法的时间复杂性和空间复杂性：

  • P 类问题：确定的图灵机在多项式时间内可判定
  • NP 类问题：不确定的图灵机在多项式时间内可判定。
  • NP 完全问题（NPC）：NP 类中某些问题的复杂性与整个类的复杂性相关联，这些问题称为NP完全问题。

关系： P $\subset$ NP, NPC $\subset$ NP, NPC $\cap$ P = $\emptyset$

P

输入规模

问题的复杂度是通过输入的规模（input size）来衡量的。
一般来说，一个问题的输入规模可以看作是编码输入的最小 01 串长度。例如，假如一个问题的输入是十进制数字 $n = \sum_{i=0}^k a_i 2^i$，那么这个问题的输入规模就是 $k = \lceil \log(n+1) \rceil - 1$。

问题类型

  • 判定问题（decision problem）：如果一个问题的输出只有是或否两种选择，那么这就是一个判定问题。
    • 如果一个判定问题在某个实例（instance，或者也可以认为是输入）下会输出“是”，那么这个输入被称为 yes-input；否则被称为 no-input。
  • 优化问题（optimization problem）：如果一个问题的输出是求某个值的最值，那么这是一个优化问题。
    • 对于几乎全部优化问题，存在一个相应的、相对简单的判定问题。例如，假如要求出最大的素数，那么响应的判定问题就是“给定一个数字，是否存在比这个数字更大的素数？”。

多项式时间算法

一个算法是多项式时间的（polynomial-time），当且仅当它的时间复杂度是 $O(n^k)$，其中 $n$ 是输入规模，$k$ 是一个与 $n$ 无关的常数。
显而易见的，无论输入规模是 $n$ 还是 $n^\alpha$，都不会影响一个算法是否是多项式时间的。

例如，两个整数的乘法的时间复杂度是 $O(m_1 m_2)$，其中 $m_1$ 和 $m_2$ 是表示两个整数所需的比特数。DFS 的时间复杂度是 $O(n+e)$。这两个算法都是多项式时间的。

反过来，假如一个算法的时间复杂度不是 $O(n^k)$，那么这个算法是非多项式时间的（non-polynomial-time）。

例如，假如我们要使用这样的算法判断数字 $N$ 是否是素数：对于每个 $2 \le K \le N - 1$，在 $\theta(\log^2 N)$ 的时间内判断 $K$ 能否整除 $N$，那么总的时间复杂度是 $\theta(N \log^2 N)$。考虑到输入规模是 $n = \log N$，因此 $\theta(N \log^2 N) = \theta(2^n n^2)$，这显然非多项式时间的。

再考虑背包问题。复杂度是 $\theta(nW)$，其中 $W$ 是背包的容量，$n$ 是物件的数量。显然输入的规模是 $size(i) = \log W + \sum \log w_i + \sum \log v_i$。输入规模不是多项式的，因此背包问题不是多项式时间的。事实上，背包问题是 NPC 问题。

如果一个问题有多项式时间算法，那么这个问题是多项式时间内可解的（solvable in polynomial time），也被称为可处理问题（tractable problems）。

定义

P 类问题是所有多项式时间可解的判定问题的集合。

The class P consists of all decision problems that are solvable inpolynomial time. That is, there exists an algorithm that will decide in polynomial time if any given input is a yes-input or a no-input.

NP

证书

证书（certificate）是一个可以用来判断一个 yes-input 是 yes-input 的中间件。

A Certificate is a specific object corresponding to a yes-input, suchthat it can be used to show that the input is indeed a yes-input.

根据定义，只有 yes-input 需要证书。

验证证书（verifying a certificate）：给定一个 yes-input 和对应的证书，我们可以根据这两者验证这个输入。

例如，假如我们要判断一个数字是否是合数，我们给定一个数字 $8$ 和对应的证书 $4$，可以根据 $8 \ \text{mod} \ 4 = 0$ 验证 $8$ 确实是一个合数。

定义

NP 类问题是判定问题的集合，每个问题的 yes-input 都存在一个相应的证书，使得我们可以在多项式时间内验证输入。

The class NP consists of all decision problems such that, for eachyes-input, there exists a certificate which allows one to verify inpolynomial time that the input is indeed a yes-input.

注意：NP 代表“非确定性多项式时间”（nondeterministic polynomial time）。

从定义可以看出，$P \subseteq NP$。

布尔可满足性问题

布尔计算式（boolean formula）是指由由布尔变量和逻辑运算符（与、或、非）组成的式子。

一个布尔计算式是可满足的（satisfiable）当且仅当存在一组布尔变量（的赋值）使得计算式的结果为真。

布尔可满足问题（satisfiability，SAT problem）：判断一个布尔计算式是否是可满足的。

Determine whether an input Boolean formula is satisfiable. lf a Boolean formula is satisfiable, it is a yes-input; otherwise, it is a no-input.

SAT 是 NP 问题。

对于每个 yes-input（可满足的布尔计算式），需要一个 01 串（证书）代表对每个变量的赋值，验证证书只需要带入计算即可，时间复杂度是 $O(n)$。
因此 SAT 是 NP 问题。

k-CNF （k-conjunctive normal form）指的是变量个数只有 $k$ 个的范式。如 3-CNF 可以是 $(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \neg x_3)$。

k-SAT 指的是当输入是 k-CNF 时的 SAT 问题。可以证明，3-SAT 是 NP 问题，2-SAT 是 P 问题。

P = NP ？

事实上，没有证明 $\text{P} = \text{NP}$ 或者 $\text{P} \ne \text{NP}$。

可能是，可能不是，全面准备吧。

NPC

规约

规约（Reduction）是一种问题之间的关系。问题 Q 可以被规约为问题 Q’ 当且仅当问题 Q 的每个实例（instance）都可以等价地转换为 Q’ 的实例。

例如，问题 Q 是乘法，问题 Q’ 是加法，Q 的每个实例可以通过 $xy = e^{\log x + \log y}$ 转换为 Q’ 的实例。

假设 L1 和 L2 是判定问题，一个从 L1 到 L2 的多项式时间规约（Polynomial-Time Reductions）指的是存在一个可以在多项式时间内计算的函数 $f$ 使得 L1 的实例可以转换为 L2 的实例，同时保持结论不变。（即 L1 的 yes-input 转换为 L2 的 yes-input，L1 的 no-input 转换为 L2 的 no-input。）如果这样的 $f$ 存在，就称 L1 可以在多项式时间内规约（polynomial-time reducible）为 L2，记作 $L_1 \le_P L_2$。

可以看出，Q’ 一定不会比 Q “更简单”。如果 Q’ 有多项式时间解法，那么 Q 也一定有。可以证明，如果 $L_1 \le_P L_2$ 且 $L_2 \le_P L_3$，那么 $L_1 \le_P L_3$。

定义

NPC 是指所有的 NP 问题都可以被多项式时间内规约为的 NP 问题（NP-complete，NP 完全问题）的集合。

The class NPC of NP-complete problems consists of all decision problems L such that
$L \in NP$ and $\forall L’ \in NP, L’ \le_P L$

如果一个 NPC 问题有多项式时间解（即这个 NPC 问题是 P 类问题），那么所有 NP 问题都有（也就是证明了 P = NP）。
反之，如果一个 NPC 问题没有多项式时间解（也就是这个问题不是 P 类问题），那么所有 NPC 问题都没有（也就是证明了 P ≠ NP），同时 $\text{P} \cap \text{NPC} = \emptyset$。

可以证明，以下问题是 NPC 问题：

  • SAT 和 3-SAT
  • DCLIQUE
  • DVC
  • DIS

NPH（NP-Hard）

一个问题是 NPH 问题当且仅当一个 NPC 问题可以多项式时间内规约到这个问题。这个问题本身不必是 NP 问题（可以是优化问题）。

A problem Lis NP-hard if problem in NPC can be polynomially reduced to it (but L does not need to be in NP)

一般来说，NPC 问题的优化问题就是 NPH 问题。如从 DVC 到 VC 问题。