常见
- 双对数:
- 多项式对数 polylog:
- 拟线性:
IMPORTANT
表示渐近性质的符号 是大写希腊字母 Omicron,而不是英文字母 。
与
- 时间指的是状态转移的次数;
- 是一个函数,表示输入规模为 情况下,算法的最差运行时间;
- 是一个函数,表示输入规模为 情况下,算法在工作带上最多使用 个格子。
- 表示存在一个图灵机在 时间内判定 。
- 表示存在一个多带图灵机在 时间内判定 。
- 表示存在一个 NTM 在 时间内判定 。
- 表示存在一个图灵机在 空间内判定 。
- 是一类函数,表示运行时间的渐近上界为 的所有函数构成的集合。
- 表示渐近下界, 当且仅当 和 。
- 对应的小写字母表示无论常数取多少都满足条件,例如 表示对任意 都有 充分大时 。
图灵停机问题
Time-constructible Functions 时间可构函数
这是函数的一个性质。
- 定义 1: 存在图灵机在输入 之后恰好执行 步后停机;
- 定义 2: 存在图灵机在输入 之后在 时间内输出 的二进制。
空间可构造函数
存在图灵机在输入 之后在 空间内输出 的二进制。
不同类型的语言
- NP: 可以在多项式时间内验证,或者由 NTM 在多项式时间内解决,即
- NP-Hard: 任何一个 NP 语言可以归约到它
- NP-Complete: NP-Hard 的 NP
- NP-Immediate: NP 但不是 NP-Hard
TIP
证明一个问题是 NP-Complete 的方法 先证明 NP,再将一个 NP-Hard 问题归约到这个问题上。
常见的 NP 问题
- SAT
- PCP
- INDSET
- CLIQUE
- HAMPATH / HAMCYCLE
- TSP
- VERTEXCOVER
- MAXCUT
- dHAMPATH(有向图上的哈密顿路径)是 NP 完全问题
常见的 NP-Immediate 问题
- 图同构
- 大整数分解
归约
定义
存在一个图灵机,对输入 满足 当且仅当 。
映射归约
符号
称 可以映射归约到 ,若有一个可计算函数 满足 当且仅当 。
图灵归约
符号
称 可以图灵归约到 ,若任意一个拥有对 有神谕的神谕图灵机都可以判定 。
NOTE
换句话说,就是如果已经可以判断是否 (即便不是用图灵机来判定),那么也可以用同样的方法来判断是否 。
部分性质:
- 若 ,则 。
- 。
Karp 归约(多项式时间映射归约)
符号
可以 Karp 归约到 的定义: 存在多项式时间的 可以把集合 变换到 ,即
Cook 归约(多项式时间图灵归约)
符号
可以 Cook 归约到 的定义:存在对 有神谕的神谕图灵机在多项式时间内判定 。
在 Karp 归约下是 NP 难当且仅当它在 Cook 归约下是 NP 难。
NOTE
Cook 归约允许在神谕图灵机上运行多项式时间,这意味着它可以至多多项式次查询神谕。而 Karp 归约相当于是一个有一个只能查询一次神谕的神谕图灵机。
可计算性
常见的不可判定语言
- 。由于 是不可判定的,而且 。所以 是不可判定的。
- 不可判定。
- 不可判定。
- 不可判定。
- 不可判定。
- 不可判定。
- 不可判定。
语言的性质
设 和 是任意两个被图灵机识别的语言。如果 满足“若 则 ”,则称 是一个性质。
如果存在 使得 且存在 使得 ,则称 是非平凡性质。
性质也是语言。
Rice 定理
非平凡性质 是不可判定的。
证明方法:证明 。
反证,假设 由图灵机 判定。
根据输入 构造一个 : 先模拟 ,如果 接收了 ,则 接着模拟任何一个 的行为,其中 ;否则模拟一个 的行为,其中 。这样,。
由于 是不可判定的,所以 也是不可判定的。
NOTE
在这个证明过程中, 是构造 用到的参数,但不是 接受的输入。
还可以把其他常见的不可判定问题归约到 上,例如 。
时间分层定理
若 和 是时间可构造函数,满足 ,则 。
空间分层定理
若 和 是空间可构造函数,满足 ,则 。