常见

  • 双对数:
  • 多项式对数 polylog:
  • 拟线性:

IMPORTANT

表示渐近性质的符号 是大写希腊字母 Omicron,而不是英文字母

  • 时间指的是状态转移的次数;
  • 是一个函数,表示输入规模为 情况下,算法的最差运行时间;
  • 是一个函数,表示输入规模为 情况下,算法在工作带上最多使用 个格子。
  • 表示存在一个图灵机在 时间内判定
  • 表示存在一个多带图灵机在 时间内判定
  • 表示存在一个 NTM 时间内判定
  • 表示存在一个图灵机在 空间内判定
  • 是一类函数,表示运行时间的渐近上界为 的所有函数构成的集合。
  • 表示渐近下界, 当且仅当
  • 对应的小写字母表示无论常数取多少都满足条件,例如 表示对任意 都有 充分大时

图灵停机问题

Time-constructible Functions 时间可构函数

这是函数的一个性质。

  • 定义 1: 存在图灵机在输入 之后恰好执行 步后停机;
  • 定义 2: 存在图灵机在输入 之后在 时间内输出 的二进制。

空间可构造函数

存在图灵机在输入 之后在 空间内输出 的二进制。

不同类型的语言

  1. NP: 可以在多项式时间内验证,或者由 NTM 在多项式时间内解决,即
  2. NP-Hard: 任何一个 NP 语言可以归约到它
  3. NP-Complete: NP-Hard 的 NP
  4. 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

在这个证明过程中, 是构造 用到的参数,但不是 接受的输入。

还可以把其他常见的不可判定问题归约到 上,例如

时间分层定理

是时间可构造函数,满足 ,则

空间分层定理

是空间可构造函数,满足 ,则