[计算理论基础] 时间复杂性

函数的阶

大 O 阶：设 $f$，$g$ 是函数、如果存在某个 $c$，$n_0$，对于任意 $n\geq n_0$，$f(n)\leq cg(n)$，则有 $f(n)=O(g(n))$

小 o 阶：$\lim_{n\to \inf}\frac{f(n)}{g(n)}=0$ 时有 $f(n)=o(g(n))$。

时间复杂性：图灵机 M 在长度为 n 的输入上运行的步数。

计算复杂性类：$TIME(t(n))=\{L|$ 某个 $O(t(n))$ 时间的单带 DTM 判定语言$L\}$

定理8.8：设函数 $t(n)\geq n$，则每个 $t(n)$ 时间多带 TM 都与某个 $O(t^2(n))$ 时间单带 TM 等价。

定理8.10：设函数 $t(n)\geq n$，则每个 $t(n)$ 时间单带 NTM 都与某个 $2^{O(t(n))}$ 时间单带 TM 等价。

P 类

定义：$P=\bigcup_k TIME(n^k)=\{L|$某个多项式时间单带 DTM 判定语言 $L\}$

---

路径问题：$PATH=\{<G,s,t>|$有向图 G 有从 s 到 t 的有向路径$\}$
定理8.12：$PATH \in P$

---

互素问题：$RELPRIME=\{<x,y>|$x y 互素$\}$
定理8.13：$RELPRIME \in P$

---

定理8.14：若 L 是 CFL，则 $L\in P$

NP 类

哈密尔路径问题：$HAMPATH=\{<G,s,t>|$有向图 G 包含从 s 到 t 的哈密尔路径$\}$
搜索规约判定：搜索问题可以规约为判定问题。

---

验证机：语言 $A = \{w |$ 某个字符串 c，算法 V 接受 $<w, c>\}$，V 是 A 的验证机，c 是 w 是 A 成员的资格证书。
多项式时间验证机：$|c|$ 是 $|w|$ 的多项式，$|w|$ 在多项式时间内运行。
如果 A 有多项式时间验证机，则 A 是多项式时间可验证的。

---

定义：$NP=\{L$ 有多项式时间验证机 $\}$

---

定理8.17：$NP=\{L$ 某个多项式时间 NTM 判定语言 $\}$
思路：验证机和多项式时间 NTM 可以互相模拟。
证明：

1. $\Rightarrow$ 在每个分支上使用验证机验证
2. $\Leftarrow$ 将 $<w, c>$ 中的 c 作为非确定图灵机的一个分支并进行模拟，根据结果进行接受或拒绝。

---

定义8.18：$NP=\bigcup_k NTIME(n^k)=\{L|$某个多项式时间单带 NTM 判定语言$L\}$

---

团问题：$CLIQUE=\{<G,k>|$无向图 G 有 k-团$\}$
定理8.20：$CLIQUE\in NP$
思路：

• 验证机：c 为一个团，对其进行验证。
• 判定机：非确定地选择 k 个顶点进行验证。

---

子集和问题：$SUBSET-SUM=\{<S,t>|$ S 中挑出子集和为 t$\}$
定理8.21：$SUBSET-SUM\in NP$
思路：

• 验证机：c 为取出的集合中的子集
• 判定机：非确定的选择子集 c，检查和是否为 t

coNP

$coNP$: NP 中的语言的补语言，$P\subseteq NP\cap coNP$

P 与 NP 问题

$P \subseteq NP \subseteq EXP = \bigcup_k TIME(2^{n^k})$
$P \neq EXP$

---

• ← Previous Post
• Next Post →