学习笔记

计算理论

6108字

计算模型

问题与决定性问题

判定性问题

只需要回答“是”或“否”的问题。

如：

  1. 一个图是否连通？
  2. 一个数是否是素数？

功能性问题

需要给出一个解决方案的问题。 如 排序，最大流，最大团等等。

本课程只讨论判定性问题。

有限自动机与正则语言

有限自动机是一个五元组$(Q, \Sigma, \delta, q_0, F)$，其中：

  1. $Q$ 是有限集，称为状态集。
  2. $\Sigma$ 是有限集，称为字母表。
  3. $\delta$ 是转移函数。
  4. $q_0 \in Q$ 是初始状态。
  5. $F \subseteq Q$ 是接受状态。

有限自动机计算的形式定义

设 $M = (Q, \Sigma, \delta, q_0, F)$ 是一个有限自动机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。

若存在 $Q$ 的一个状态序列 $r_0, r_1, \cdots, r_n$，使得：

  1. $r_0 = q_0$。
  2. $r_{i+1} = \delta(r_i, w_{i+1})$，对 $i = 0, 1, \cdots, n-1$。
  3. $r_n \in F$。

则称 $M$ 接受字符串 $w$。 记为 $\delta(r_0, w) \in F$。

识别语言

对于一个有限自动机 $M$，若 $A = \lbrace w \in \Sigma^* | \delta(q_0, w) \in F \rbrace$，则称 $A$ 是 $M$ 的语言，记为 $L(M) = A$，也称 $M$ 识别 $A$。

$M$ 识别的语言唯一，不识别任意其他语言。

正则语言

若存在一个有限自动机 $M$，使得 $L(M) = A$，则称 $A$ 是一个正则语言。

等价

若两个有限自动机的语言相同，则称它们是等价的。

正则运算

  1. 并：$A \cup B = \lbrace w | w \in A \text{ 或 } w \in B \rbrace$。
  2. 连接：$A \circ B = \lbrace w | w = w_1w_2, w_1 \in A, w_2 \in B \rbrace$。
  3. 星号：$A^* = A^0 \cup A^1 \cup A^2 \cup \cdots$，其中 $A^0 = \lbrace \varepsilon \rbrace$，$A^1 = A$，$A^2 = A \circ A$。 即 $A^*=\lbrace w_1w_2\cdots w_n | n \ge 0, w_i \in A \rbrace$。
  4. 补：$A^c = \Sigma^* - A$。

正则语言对这四种运算封闭。 则相对补与对称差运算也是封闭的。 即 $A - B = A \cap B^c$，$A \oplus B = (A - B) \cup (B - A)$。

非确定性

当机器处于给定的状态并读入下一个输入符号时，可以知道机器的下一个状态是什么——它是确定的。因此，称这是确定型计算 $\mathrm{(deterministic computation)}$。在非确定型$\mathrm{(nondeterministic)}$机器中，在任何一点，下一个状态可能存在若干个选择。

确定型有限自动机：$\mathrm{(Deterministic Finite Automaton, DFA)}$ 非确定型有限自动机：$\mathrm{(Nondeterministic Finite Automaton, NFA)}$

非确定性是确定性的推广，因此每一台 $\mathrm{DFA}$ 自动地是一台 $\mathrm{NFA}$ 。

确定型有限自动机 (DFA)

$\delta: Q \times \Sigma \to Q$ 是一个函数，对于每一个 $q \in Q$ 和 $\sigma \in \Sigma$，$\delta(q, \sigma)$ 是唯一的。

非确定型有限自动机 (NFA)

$\delta: Q \times \Sigma_\varepsilon \to P(Q)$ 是一个函数，对于每一个 $q \in Q$ 和 $\sigma \in \Sigma_\varepsilon$，$\delta(q, \sigma)$ 是一个状态集合，可能进入多个状态。

转移箭头函数上的符号可以是 $\varepsilon$，表示可以不读入任何输入就转移。

NFA的计算方式

  1. 若读到输入字符 $s$，机器把自己备份 $0$ 次或多次，然后从这些备份中选择一个状态，继续读入下一个字符。
  2. 若读到 $\varepsilon$，机器将自己备份一次，然后继续读入下一个字符。
  3. 读入下一个输入符号，若该符号存在于备份状态的转移函数中，则转 $1$，否则停机。
  4. 机器检查是否有一个备份状态是接受状态。若存在一个副本是接受状态，则接受输入。

对于输入，$\mathrm{NFA}$ 计算的路径可能不唯一。

NFA 与 DFA 等价

对于每一个 $\mathrm{NFA}$，都存在一个等价的 $\mathrm{DFA}$。

子集构造法

$\mathrm{NFA}$：$\mathrm{N} = (Q, \Sigma, \delta, q_0, F)$ $\mathrm{DFA}$：$\mathrm{M} = (Q’, \Sigma, \delta’, q_0’, F’)$

  1. $Q’ = 2^Q$，即 $\mathrm{DFA}$ 的状态集是 $\mathrm{NFA}$ 的状态集的幂集。
  2. $E$ 表示 $\varepsilon$ 闭包，即 $E(S) = \lbrace q \ |\ q \in S \text{ 或 } q \text{ 可以通过若干个 }\varepsilon\text{ 转移到 } S \rbrace$。
  3. $q_0’ = E(\lbrace q_0 \rbrace)$。
  4. $\delta’(S, a) = E(\bigcup_{q \in S} \delta(q, a))$，其中 $S \in Q’$，$a \in \Sigma$。
  5. $F’ = \lbrace S \in Q’ \ |\ S \cap F \neq \varnothing \rbrace$。

正则表达式

若 $R$ 是一个正则表达式，则 $R$ 是

  1. $a, a \in \Sigma$。
  2. $\varepsilon$。
  3. $\varnothing$。
  4. $(R_1 \cup R_2)$, $R_1$ 和 $R_2$ 是正则表达式。
  5. $(R_1 \circ R_2)$, $R_1$ 和 $R_2$ 是正则表达式。
  6. $(R_1^*)$，$R_1$ 是正则表达式。

每个正则表达式 $R$ 表示一种正则语言 $L(R)$。

  1. $L(a) = \lbrace a \rbrace$。
  2. $L(\varepsilon) = \lbrace \varepsilon \rbrace$。
  3. $L(\varnothing) = \varnothing$。
  4. $L(R_1 \cup R_2) = L(R_1) \cup L(R_2)$。
  5. $L(R_1 \circ R_2) = L(R_1) \circ L(R_2)$。
  6. $L(R_1^*) = (L(R_1))^*$。

正则表达式与有限自动机等价

－个语言是正则的，当且仅当可以用正则表达式描述它。

由正则表达式构造有限自动机
由正则表达式构造有限自动机
由有限自动机构造正则表达式
由有限自动机构造正则表达式

泵引理

若 $A$ 是一个正则语言，则存在一个整数 $p$，使得对于任意 $w \in A$，若 $|w| \ge p$，则 $w$ 可以被分解为 $w = xyz$，满足：

  1. 对于任意 $i \ge 0$，$xy^iz \in A$。
  2. $|y| > 0$。
  3. $|xy| \le p$。

图灵机

图灵机 $\mathrm{(Turing Machine, TM)}$ 是一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，其中：

  1. $Q$ 是有限集，称为状态集。
  2. $\Sigma$ 是有限集，称为输入字母表，不包含特殊空白符号 $\sqcup$。
  3. $\Gamma$ 是有限集，称为带子字母表，$\Sigma \subseteq \Gamma$，且 $\sqcup \in \Gamma - \Sigma$。
  4. $\delta: Q \times \Gamma \to Q \times \Gamma \times \lbrace L, R \rbrace$ 是转移函数。即 $\delta(q, a) = (r, b, L / R)$ 表示在状态 $q$ 读入字符 $a$ 后，将字符 $a$ 替换为字符 $b$，转移到状态 $r$，第三个参数 $L / R$ 表示下一步向左 / 向右移动。
  5. $q_0 \in Q$ 是初始状态。
  6. $q_{\text{accept}} \in Q$ 是接受状态。
  7. $q_{\text{reject}} \in Q$ 是拒绝状态，且 $q_{\text{reject}} \neq q_{\text{accept}}$。

图灵机的初始化

设 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ 是一个图灵机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。

  1. 输入带：将 $w$ 放在最左端，其余位置填充 $\sqcup$。
  2. 状态：初始状态为 $q_0$。
  3. 读写头：指向第一个字符 $w_1$。

图灵机的格局

对于一个图灵机 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，设 $q \in Q$ ， $u, v \in \Gamma^*$， 则 格局 $uqv$ 表示：

  1. 状态：$q$。
  2. 存储带：存储带上的内容为 $uv$，其余为空白符号 $\sqcup$。
  3. 读写头：指向 $v$ 的第一个字符。

格局的分类

  • 起始格局：$q_0w$。
  • 接受格局：$uq_{\text{accept}}v$。
  • 拒绝格局：$uq_{\text{reject}}v$。
  • 停机格局：$uqv$，其中 $q \in \lbrace q_{\text{accept}}, q_{\text{reject}} \rbrace$。

格局的转移

  • 如果 $\delta(q_i, b) = (q_j, c, L)$，则
    • $u\textcolor{yellow}{aq_ib}v \to u\textcolor{orange}{q_jac}v$
    • $\textcolor{yellow}{q_ib}v \to \textcolor{orange}{q_jc} v$
  • 如果 $\delta(q_i, b) = (q_j, c, R)$，则
    • $u\textcolor{yellow}{aq_ib}v \to u\textcolor{orange}{acq_j}v$

图灵机的计算

设 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ 是一个图灵机，$w = w_1w_2\cdots w_n$ 是一个字符串，其中 $w_i \in \Sigma$。

若存在格局序列 $C_1, C_2, \cdots, C_k$，使得

  1. $C_1 = q_0w$。
  2. 对于 $i = 1, 2, \cdots, k-1$，$C_i \to C_{i+1}$。
  3. $C_k$ 是停机格局。

则称 $M$ 接受字符串 $w$。

图灵机 $M$ 接受 的所有字符串的集合称为 $M$ 接受 / 识别 的语言，记为 $L(M)$。

图灵机运行的结果

  • 若 $\mathrm{TM}$ 进入接受状态，则停机且接受输入。
  • 若 $\mathrm{TM}$ 进入拒绝状态，则停机且拒绝输入。
  • 否则，$\mathrm{TM}$ 一直运行，不停机。

若图灵机 $M$ 对所有输入都停机，则称 $M$ 是判定器。
即对于任意输入，$M$ 要么接受，要么拒绝，不会无限循环。

对于可以识别某个语言的判定器 $M$，称 $M$ 判定该语言。

语言的分类

  • 图灵可识别语言：存在一个图灵机可以识别该语言。

    • 也称递归可枚举语言。
      • = 递归可枚举
      • = 计算可枚举
      • = 半可判定
      • = 半可计算

  • 图灵可判定语言：存在一个图灵机可以判定该语言。

    • 也称递归语言。
      • = 递归
      • = 可解
      • = 可行
      • = 可判定
      • = 可计算

包含关系：

graph TD
    subgraph turing_recognizable["图灵可识别语言"]
        subgraph turing_decidable["图灵可判定语言"]
            regex_language["正则语言"]
        end
    end
    classDef circleStyle fill:#dd1,color:black,stroke:#333,stroke-width:4px;

    class turing_recognizable circleStyle;
    class turing_decidable circleStyle;
    class regex_language circleStyle;

图灵机的描述

  1. 形式水平的描述：状态图或转移函数
  2. 实现水平的描述：读写头的移动与读写，状态的转移
  3. 高水平的描述：使用日常语言描述 例如

$M$ = “对于输入串 $w$

  1. 若 $w$ = $\epsilon$，则接受
  2. 若只有一个 $0$，则接受
  3. 若 $0$ 的个数是奇数，则拒绝
  4. 从带左端隔一个 $0$ 删除一个 $0$，转移到步骤 $2$”

由定义，图灵机的输入总是字符串。
有时候要输入数，图，或图灵机等对象，要将对象编码成字符串。
记对象 O 的编码为 <O>。

特别的，图灵机是有向带权图也可以编码为字符串。

输入为对象的图灵机举例

非确定性图灵机

非确定性图灵机 $\mathrm{(Nondeterministic Turing Machine, NTM)}$ 是一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$，它的转移函数是 $\delta: Q \times \Gamma \to P(Q \times \Gamma \times \lbrace L, R \rbrace)$。

如果计算的某个分支导致接受状态，则机器接受该输入。

非确定性图灵机举例

称 $\mathrm{NTM}$ $M$接受 $x$ ， 若在 $x$ 上运行 $M$ 时有接受分支。
称一个 $\mathrm{NTM}$ 为判定的，若它对所有输入，所有分支都停机。

每个 $\mathrm{NTM}$ 都有等价的 $\mathrm{DTM}$
每个判定 $\mathrm{NTM}$ 都有等价的判定 $\mathrm{DTM}$

图灵可识别当且仅当可用非确定型图灵机识别。
图灵可判定当且仅当可用非确定型图灵机判定。

可计算性

可判定性

可判定性问题是指是否存在一个算法，能够判定一个给定的问题的实例是否属于问题的解集。
如果存在这样的算法，那么这个问题就是可判定的。
否则，这个问题就是不可判定的。
我们使用图灵机来 描述 可判定性问题。 如果一个语言可以被图灵机判定，那么这个语言是可判定的。否则，这个语言是不可判定的。

与正则语言相关的可判定性问题

  1. $A_{\mathrm{DFA}} = \lbrace \langle B, w \rangle \ |\ B \text{ 是一个 DFA，且 } B \text{ 接受字符串 } w \rbrace$
    判定 $A_{\mathrm{DFA}}$ 即判断 $w$ 是否是 $B$ 的一个接受字符串。
    是可判定的。

  2. $A_{\mathrm{NFA}} = \lbrace \langle B, w \rangle \ |\ B \text{ 是一个 NFA，且 } B \text{ 接受字符串 } w \rbrace$
    判定 $A_{\mathrm{NFA}}$ 即判断 $w$ 是否是 $B$ 的一个接受字符串。
    是可判定的。

  3. $A_{\mathrm{REX}} = \lbrace \langle R, w \rangle \ |\ R \text{ 是一个正则表达式，且 } R \text{ 接受字符串 } w \rbrace$
    判定 $A_{\mathrm{REX}}$ 即判断 $w$ 是否是 $R$ 的一个接受字符串。
    是可判定的。

  4. $E_{\mathrm{DFA}} = \lbrace \langle B \rangle \ |\ B \text{ 是一个 DFA，且 } L(B) = \varnothing \rbrace$
    判定 $E_{\mathrm{DFA}}$ 即判断 $L(B) = \varnothing$。
    是可判定的。

  5. $EQ_{\mathrm{DFA}} = \lbrace \langle B_1, B_2 \rangle \ |\ B_1 \text{ 和 } B_2 \text{ 是 DFA，且 } L(B_1) = L(B_2)\rbrace$
    判定 $EQ_{\mathrm{DFA}}$ 即判断 $L(B_1) = L(B_2)$， 即 $L(B_1) \oplus L(B_2) = \varnothing$。
    是可判定的。

对角化方法

如果存在函数 $f : A \to B$，且 $f$ 是一对一映射又是满映射，则称集合 $A$ 和 $B$ 有相同规模。

如果一个集合A 是有限的或者与 $\mathbb{N}$ 有相同的规模，则称 $A$ 是可数的 如： 有理数集 $\mathbb{Q}$ 是可数的，因为可以通过一一对应的方式将有理数映射到 $\mathbb{N}$。
实数集 $\mathbb{R}$ 是不可数的，因为实数集比有理数集大。

存在不能被任何图灵机识别的语言

  1. 所有图灵机构成的集合是可数的
    • 对任意的字母表 $\Sigma$ ，其上所有串 $\Sigma^*$ 的集合是可数的
  2. 所有语言构成的集合是不可数的
    • 对任意的字母表 $\Sigma$ ，其上所有语言 $\mathcal{P}(\Sigma^*)$ 的集合是不可数的

规约

$P \le_m Q$ 表示 $P$ 可规约到 $Q$。
若 $P$ 是不可判定的，则 $Q$ 也是不可判定的。
若 $Q$ 是可判定的，则 $P$ 也是可判定的。
$P$ 是 $Q$ 的一个特例，$Q$ 是 $P$ 的一个一般化。

与图灵机相关的不可判定性问题

$A_{\mathrm{TM}}$

$A_{\mathrm{TM}} = \lbrace \langle M, w \rangle \ |\ M \text{ 是一个图灵机，且 } M \text{ 接受字符串 } w \rbrace$ 判定 $A_{\mathrm{TM}}$ 即判断 $w$ 是否是 $M$ 的一个接受字符串。 是不可判定的。

可识别

使用如下算法可以识别 $A_{\mathrm{TM}}$：

  1. 令 $U$ 是一个图灵机，对于任意输入 $\langle M, w \rangle$，$U$ 模拟 $M$ 运行 $w$。
  2. 若 $M$ 接受 $w$，则 $U$ 接受 $\langle M, w \rangle$。
  3. 若 $M$ 拒绝 $w$，则 $U$ 拒绝 $\langle M, w \rangle$。

如果 $M$ 在 $w$ 上循环，则 $U$ 也会在 $\langle M, w \rangle$ 上循环，这就是为什么 $A_{\mathrm{TM}}$ 是不可判定的。

不可判定
ATM不可判定

$HALT_{\mathrm{TM}}$

$HALT_{\mathrm{TM}} = \lbrace \langle M, w \rangle \ |\ M \text{ 是一个图灵机，且 } M \text{ 在输入 } w \text{ 上停机} \rbrace$ 可识别，但是不可判定的。 $A_{\mathrm{TM}}$ 可以规约到 $HALT_{\mathrm{TM}}$。 所以 $HALT_{\mathrm{TM}}$ 是不可判定的。 即 $A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}$。

$E_{\mathrm{TM}}$

$E_{\mathrm{TM}} = \lbrace \langle M \rangle \ |\ M \text{ 是一个图灵机，且 } L(M) = \varnothing \rbrace$ 是不可判定的。
$A_{\mathrm{TM}}$ 可以规约到 $E_{\mathrm{TM}}$。

补图灵可识别

对任意不可判定的语言 $A$，它和它的补集 $\overline{A}$ 至少有一个不是图灵可识别的。

如果一个语言是一个图灵可识别的语言的补集，那么这个语言是补图灵可识别的。

－个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。

$\overline{A_{\mathrm{TM}}}$ 不是图灵可识别的。

可知：图灵可识别的补运算不封闭。

计算复杂性

时间复杂性

度量复杂性

时间复杂度

令 $M$ 是一个在所有输入上都停机的确定型图灵机。$M$ 的运行时间或者时间复杂度是一个函数 $f: \mathbb{N} \to \mathbb{N}$。
其中 $\mathbb{N}$ 是非负整数集合，$f(n)$ 是 $M$ 在所有长度为 $n$ 的输入上运行时所经过的最大步数。
若 $f(n)$ 是 $M$ 的运行时间，则称 $M$ 在时间 $f(n)$ 内运行，$M$ 是 $f(n)$ 时间图灵机。 通常使用 $n$ 表示输入的长度。

大 $O$ 和小 $o$ 记法

因为算法精确运行时间通常是一个复杂的表达式，所以一般只估计它的趋势和级别。
通过 渐近分析 ， 只考虑算法的时间的表达式的最高次项，忽略低次项和常数系数，可以试图了解算法在长输入上的运行时间。

  1. 大 $O$ 记法：
    令 $f(n)$ 和 $g(n)$ 是定义在非负整数集合上的函数。
    $f(n)=O(g(n))$ 当且仅当存在一个常数 $c>0$ 和一个整数 $n_0 \ge 0$，使得对于所有的 $n \ge n_0$，有 $f(n) \le cg(n)$。
  2. 小 $o$ 记法：
    $f(n)=o(g(n))$ 当且仅当对于所有的常数 $c>0$，存在一个整数 $n_0 \ge 0$，使得对于所有的 $n \ge n_0$，有 $f(n) < cg(n)$。
    或 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$。 $$f(n) \neq o(f(n))$$

时间复杂性类

$$\mathrm{TIME}(f(n)) = \lbrace L \ | \ \text{ 存在确定性 } O(f(n)) \text{ 时间图灵机判定 } L \ \rbrace$$

P 类

$\mathrm{P}$ 类是单带确定 $\mathrm{TM}$ 在所有可以在多项式时间内判定的问题的集合。 $$\mathrm{P} = \bigcup_{k \in \mathbb{N}} \mathrm{TIME}(n^k)$$

重要性

  1. 对于 所有 与单带确定 $\mathrm{TM}$ 等价的 模型，$\mathrm{P}$ 类是相同的。
    • 无论你使用的是单带图灵机、多带图灵机，还是其他等价的计算模型，只要一个问题在某个模型上可以在多项式时间内判定（属于 P 类问题），那么在其他模型上也可以在多项式时间内判定。
  2. $\mathrm{P}$ 类大致对应于计算机上 $实际可解$ 的问题。

NP 类

$\mathrm{NP}$ 类是单带非确定 $\mathrm{TM}$ 在所有可以在多项式时间内判定的问题的集合。 $$\mathrm{NP} = \bigcup_{k \in \mathbb{N}} NTIME(n^k)$$ 其中 $NTIME(f(n))$ 是非确定性图灵机在时间 $f(n)$ 内可以接受的语言的集合。 $$NTIME(f(n)) = \lbrace L \ | \ \text{ 存在非确定性 } O(f(n)) \text{ 时间图灵机判定 } L \ \rbrace$$

非确定性图灵机中猜测的步骤不算做时间复杂度。 例如选取一个子集 / 一个路径 / 一个排列等。

$\mathrm{NP}$ 类中的问题是可以在多项式时间内验证的问题。

$$\mathrm{P} \subseteq \mathrm{NP}$$ $\mathrm{P} = \mathrm{NP} ?$ 是一个重要的未解问题。

验证机

$$A = \lbrace w \ | \ \text{存在一个证明字符串 } c \text{ 使得 } M \text{ 在输入 } \langle w, c \rangle \text{ 上接受} \rbrace$$ 称 $M$ 是 $A$ 的验证机。

判断一个问题是否属于 $\mathrm{NP}$ 类，可以通过构造 $\mathrm{NTM}$ 或者验证机来判断。

$\mathrm{CLIQUE} \in \mathrm{NP}$

CLIQUE1 CLIQUE2

$\mathrm{HP} \in \mathrm{NP}$

HP

coNP 类

$$\mathrm{coNP} = \lbrace L \ | \ \overline{L} \in \mathrm{NP} \rbrace$$ $\mathrm{NP} =? \mathrm{coNP}$ 是一个重要的未解问题。 $$\mathrm{P} \subseteq \mathrm{NP} \cap \mathrm{coNP}$$

NP 完全问题

$\mathrm{NP}$ 中某些问题的复杂性与整个 $\mathrm{NP}$ 类的复杂性相关联，即：
若这些问题中的任一个找到 $\mathrm{P}$ 时间算法，则 $\mathrm{P} = \mathrm{NP}$。
这些问题称为 $\mathrm{NP}$ 完全问题。

$\mathrm{SAT}$ 问题

$$\mathrm{SAT} = \lbrace \phi \ | \ \phi \text{ 是一个可满足的布尔公式} \rbrace$$

理论意义

  1. 研究 $\mathrm{P}$ 和 $\mathrm{NP}$ 之间的关系可以只关注于一个问题的算法。
  2. 由此可以说明一个问题目前还没有找到 $\mathrm{P}$ 时间算法。

多项式时间归约

类似于 问题的规约 ，多项式时间规约定义了问题求解的有效性传递。

若存在多项式时间图灵机 $\mathrm{M}$ 使得在任意输入 $w$ 上， $\mathrm{M}$ 停机时，带子上显示的字符串为 $f(w)$ ，则称函数 $f: \Sigma^* \to \Sigma^*$ 为多项式时间可计算函数。

称 $A$ 可多项式时间映射规约到 $B$，记作 $A \le_p B$，若 $$\exists f:\Sigma^* \to \Sigma^* \text{ 使得 } \forall w \in \Sigma^*, \quad w \in A \Leftrightarrow f(w) \in B$$ 函数 $f$ 称为 $A$ 到 $B$ 的多项式时间归约。

即 $f$ 将 $A$ 的实例编码在多项式时间内转换为 $B$ 的实例编码。

P 类问题的多项式时间归约

若 $A \le_p B$ 且 $B \in \mathrm{P}$，则 $A \in \mathrm{P}$。 若 $A \le_p B$ 且 $B \in \mathrm{NPC}$，则 $A \in \mathrm{NPC}$。

© 2025 Reina
使用 Hugo 构建
主题 Stack 由 Jimmy 设计