Time Complexity

Measuring Complexity

Three levels of analysis

Define three functions:

  • \(f_1 : \Sigma^* \to \mathbb{N}\) — exact running time on each input

    • For every input string \(x \in \Sigma^*\), \(f_1(x)\) is the number of steps \(M\) uses on \(x\).

  • \(f_2 : \mathbb{N} \to \mathbb{N}\) — worst-case running time by input length

    • \(f_2(n) = \max{ f_1(x) : x \in \Sigma^n }\)

  • \(f_3 : \mathbb{N} \to \mathbb{N}\) — average-case running time by input length

    • \[f_3(n) = \frac{\sum_{x \in \Sigma^n} f_1(x)}{|\Sigma|^n}\]

理论计算复杂度里，默认讨论的是 \(f_2\)（最坏情况），因为它有良好的上界性质和组合结构。

Worst-case time complexity

NoteDefinition: Running Time of a TM

Let \(M\) be a deterministic Turing machine that halts on all inputs. The running time (or time complexity) of \(M\) is the function \(f : \mathbb{N} \to \mathbb{N}\), where \(f(n)\) is the maximum number of steps that \(M\) uses on any input of length \(n\).

If \(f(n)\) is the running time of \(M\), we say that \(M\) runs in time \(f(n)\) and that \(M\) is an \(f(n)\) time Turing machine.

Customarily, we use \(n\) to represent the length of the input.

  • We restrict to deciders (machines that halt on all inputs), so \(f(n)\) is well-defined.
  • Input length is denoted by \(n\).
  • When we say “\(M\) runs in time \(f(n)\)”, we mean \(M\) never exceeds \(f(n)\) steps on inputs of length \(n\).

Big-O notation

NoteDefinition: Big-O Notation

Let \(f, g : \mathbb{N} \to \mathbb{R}^+\) be two functions. We say that \(f(n) = O(g(n))\) if there exist positive integers \(c\) and \(n_0\) such that for every integer \(n \ge n_0\): \[f(n) \le c \cdot g(n).\]

When \(f(n) = O(g(n))\), we say that \(g(n)\) is an upper bound for \(f(n)\), or more precisely, that \(g(n)\) is an asymptotic upper bound for \(f(n)\), to emphasize that we are suppressing constant factors.

Little-o notation

NoteDefinition: Little-o Notation

\(f(n) = o(g(n))\) iff \(\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.\)

\(f\) grows strictly slower than \(g\); \(g\) dominates \(f\).

Big-O Examples:

  1. \(5n^3 + 2n^2 + 22n + 6 = O(n^3)\)
  2. \(\log_b n = O(\log n)\)（对数换底只差常数因子）
  3. \(3n \log_2 n + 5n \log_2 \log_2 n + 2 = O(n \log n)\)
  4. \(2^{10n^2 + 7n - 6} = 2^{O(n^2)}\)

Little-o Examples（严格增长序）:

\(\sqrt{n} = o(n)\), \(\;n = o(n \log\log n)\), \(\;n \log\log n = o(n \log n)\), \(\;n \log n = o(n^2)\), \(\;n^2 = o(n^3)\)

Polynomial vs Exponential bounds: \(n^c\)（\(c > 0\)）是多项式界，\(2^{n^\delta}\)（\(\delta > 0\)）是指数界。

Example: \(A = \{0^k 1^k | k \ge 0\}\)

on a single tape TM

Naive Algorithm

朴素成对划消

  1. Scan to verify input is of form \(0^*1^*\) — \(O(n)\)
  2. Repeatedly cross off one \(0\) and one \(1\) until none remain — each pass is \(O(n)\), with \(O(n)\) passes
  3. Accept if no symbols remain — \(O(n)\)

Total time: \(O(n^2)\)

Improved Algorithm (Single-Tape)

每轮删除一半符号

  1. Scan to verify input is of form \(0^*1^*\) — \(O(n)\)
  2. Repeat until all symbols are crossed off:
    • If the total count of remaining \(0\)s and \(1\)s is odd, reject
    • Cross off every other \(0\) and every other \(1\) — \(O(n)\)
  3. Accept if no symbols remain — \(O(n)\)

Each pass halves the remaining symbols, so there are \(O(\log n)\) passes.

Total time: \(O(n \log n)\)

Improved Algorithm (Multi-Tape)

  1. Copy all \(0\)s to tape 2 — \(O(n)\)
  2. Copy all \(1\)s to tape 3 — \(O(n)\)
  3. Scan tape 2 and tape 3 simultaneously, crossing off one \(0\) and one \(1\) per step — \(O(n)\)
  4. Accept if both tapes finish together — \(O(1)\)

Total time: \(O(n)\)

Time complexity classes: TIME(t(n))

NoteDefinition: Time Complexity Class TIME(t(n))

Let \(t : \mathbb{N} \to \mathbb{R}^+\) be a function. Define the time complexity class \[\mathrm{TIME}(t(n))\] to be the collection of all languages that are decidable by an \(O(t(n))\) time Turing machine.

Example: \(\{0^k 1^k \mid k \ge 0\} \in \mathrm{TIME}(n^2)\).

Lower bounds of single-tape TM

ImportantTheorem: Single-Tape TM Lower Bound

Every language that can be decided in \(o(n \log n)\) time on a single-tape Turing machine is regular.

Proof idea: The key insight is that a single-tape TM must move its head back and forth to compare symbols in different parts of the input.

  1. Crossing sequence argument: For any computation on input \(w\), define the crossing sequence at position \(i\) as the sequence of states the TM is in each time it crosses the boundary between positions \(i\) and \(i+1\).

  2. Bounded crossing sequences: If the TM runs in time \(t(n)\), the total number of crossings across all boundaries is at most \(t(n)\). By pigeonhole, for inputs of length \(n\), there exists some boundary crossed at most \(t(n)/n\) times.

  3. Key lemma: If two inputs \(w_1\) and \(w_2\) have the same crossing sequence at some position, then swapping their prefixes/suffixes preserves acceptance behavior.

  4. Counting argument: If \(t(n) = o(n \log n)\), then crossing sequences have length \(o(\log n)\). With \(|Q|\) states, there are at most \(|Q|^{o(\log n)} = n^{o(1)}\) distinct crossing sequences.

  5. Myhill-Nerode application: Since the number of distinct crossing sequences grows sublinearly, the number of equivalence classes under the Myhill-Nerode relation is finite, implying the language is regular.

Contrapositive: Since \(\{0^k1^k\}\) is not regular (by the pumping lemma), any single-tape TM deciding it requires \(\Omega(n \log n)\) time.

如果一个单带图灵机（Single-tape TM）处理语言的时间复杂度太低，以至于它无法在磁带上进行有效的“跨区域”信息传递，那么它在本质上就退化成了一个有限自动机（DFA）。

Complexity relationships among models

ImportantTheorem

Let \(t(n)\) be a function with \(t(n) \geq n\). Every \(t(n)\) time multitape Turing machine has an equivalent single-tape Turing machine that runs in time \(O(t(n)^2)\).

设 \(M\) 是一个运行时间为 \(t(n)\) 的 \(k\) 带图灵机。我们构造一个单带图灵机 \(S\) 来模拟 \(M\)。

  1. 带子表示： \(S\) 将 \(M\) 的所有 \(k\) 条带子存储在一条带子上，用分隔符 # 隔开。带子内容形如： \[ \# w_1 \# w_2 \# \cdots \# w_k \# \]

    其中 \(w_i\) 是第 \(i\) 条带子的内容。

  2. 磁头位置标记： 对于每条带子 \(i\)，我们用”带点版本”的符号来标记当前磁头位置。若原字母表为 \(\Gamma\)，则扩展为 \(\Gamma \cup \dot{\Gamma}\)，其中 \(\dot{a}\) 表示磁头正在扫描符号 \(a\)。

  3. 单步模拟： 为了模拟 \(M\) 的一步，模拟器 \(S\)：

    • 从左到右扫描整条带子，找到所有 \(k\) 个带点符号（磁头位置），记录被读取的符号。
    • 根据 \(M\) 的转移函数，确定新状态、要写入的符号和磁头移动方向。
    • 再次扫描，更新每条带子：写入新符号并相应移动点标记。

  4. 时间分析：

    • \(M\) 运行 \(t(n)\) 步后，每条带子最多包含 \(t(n)\) 个符号（因为磁头每步最多移动一格）。
    • \(S\) 的总带子长度为 \(O(k \cdot t(n)) = O(t(n))\)（因为 \(k\) 是常数）。
    • 每次模拟需要对 \(O(t(n))\) 个格子进行两次扫描，耗时 \(O(t(n))\)。
    • 总模拟时间：\(t(n) \times O(t(n)) = O(t(n)^2)\)。

因此，\(S\) 的运行时间为 \(O(t(n)^2)\)。

\(\square\)

Nondeterministic Turing Machines

Definition: Let \(N\) be a nondeterministic Turing machine that is a decider. The running time of \(N\) is the function \(f : \mathbb{N} \to \mathbb{N}\), where \(f(n)\) is the maximum number of steps that \(N\) uses on any branch of its computation on any input of length \(n\).

flowchart TD
    q0["Initial config (q₀, w)"]
    q0 --> c1["Config 1"]
    q0 --> c2["Config 2"]
    q0 --> c3["Config 3"]
    c1 --> acc1(("Accept"))
    c2 --> c21["Config 2.1"]
    c2 --> c22["Config 2.2"]
    c3 --> c31["Config 3.1"]
    c3 --> c32["Config 3.2"]
    c3 --> c33["Config 3.3"]
    c21 --> acc2(("Accept"))
    c22 --> rej1(("Reject"))
    c31 --> rej2(("Reject"))
    c32 --> c321["..."]
    c33 --> rej3(("Reject"))
    c321 --> rej4(("Reject"))
    
    style acc1 fill:#90EE90
    style acc2 fill:#90EE90
    style rej1 fill:#FFB6C1
    style rej2 fill:#FFB6C1
    style rej3 fill:#FFB6C1
    style rej4 fill:#FFB6C1
    
    %% f(n) path - longest branch
    linkStyle 2 stroke:#FF6600,stroke-width:3px
    linkStyle 7 stroke:#FF6600,stroke-width:3px
    linkStyle 12 stroke:#FF6600,stroke-width:3px
    linkStyle 14 stroke:#FF6600,stroke-width:3px

NTM Computation Tree: f(n) is the maximum depth

The running time \(f(n)\) of an NTM is the height of the tallest branch in this computation tree. Each node represents a configuration, and each edge represents a nondeterministic choice. The NTM accepts if any branch reaches an accept state.

ImportantTheorem

Let \(t(n)\) be a function with \(t(n) \geq n\). Then every \(t(n)\) time nondeterministic single-tape Turing machine has an equivalent \(2^{O(t(n))}\) time deterministic single-tape Turing machine.

证明思路： 我们通过确定性地模拟非确定性图灵机的所有可能计算分支来构造等价的确定性图灵机。

设 \(N\) 是一个运行时间为 \(t(n)\) 的非确定性单带图灵机，设 \(b\) 为 \(N\) 在任意配置下的最大分支数（即转移函数在任意状态-符号对上最多有 \(b\) 个可能的转移）。

1. 计算树结构：

\(N\) 在输入 \(w\)（长度为 \(n\)）上的计算可以表示为一棵树：

  • 根节点是初始配置
  • 每个节点最多有 \(b\) 个子节点（对应非确定性选择）
  • 树的高度最多为 \(t(n)\)（因为 \(N\) 的运行时间为 \(t(n)\)）

2. 构造确定性模拟器 \(D\)：

\(D\) 使用三条带子：

  • 带子 1： 存储输入 \(w\)
  • 带子 2： 模拟 \(N\) 的工作带
  • 带子 3： 存储当前分支的”地址”——一个长度最多为 \(t(n)\) 的字符串，字符取自 \(\{1, 2, \ldots, b\}\)

3. 模拟过程：

\(D\) 按字典序枚举所有可能的地址字符串：

  • 对于每个地址 \(a_1 a_2 \cdots a_m\)（其中 \(m \leq t(n)\)）
  • 在带子 2 上复制输入，然后模拟 \(N\)
  • 在第 \(i\) 步，如果 \(N\) 有多个可能转移，选择第 \(a_i\) 个转移
  • 如果该分支到达接受状态，\(D\) 接受
  • 如果该分支拒绝或地址用完，尝试下一个地址

4. 时间分析：

  • 计算树中的节点总数最多为 \(1 + b + b^2 + \cdots + b^{t(n)} = O(b^{t(n)})\)
  • 模拟每个分支需要 \(O(t(n))\) 步
  • 总时间：\(O(t(n) \cdot b^{t(n)}) = O(t(n) \cdot 2^{t(n) \log b}) = 2^{O(t(n))}\)

由于 \(b\) 是常数（取决于 \(N\) 的转移函数），\(\log b\) 也是常数，因此总运行时间为 \(2^{O(t(n))}\)。

\(\square\)

经典包含关系： \[\mathrm{NTIME}(t(n)) \subseteq \mathrm{TIME}(2^{O(t(n))}).\]

NoteDefinition: NTIME

\[\mathrm{NTIME}(t(n)) = \{ L \mid L \text{ is decided by an } O(t(n)) \text{ time nondeterministic TM} \}\]

Corollary: \(\mathrm{NP} = \bigcup_{k \in \mathbb{N}} \mathrm{NTIME}(n^k)\)。

Class P

\[\mathrm{P} = \bigcup_{k \in \mathbb{N}} \mathrm{TIME}(n^k).\]

  • P is the set of languages decidable in polynomial time by a deterministic single-tape TM.
  • Because of model equivalence, P is robust under many reasonable machine models.

Reasonable encodings（合理编码）：

  • Unary encoding 是不合理的——将数 \(n\) 编码为 \(1^n\)，长度为 \(n\)，而 binary 编码长度仅为 \(\log n\)。一元编码人为地增大了输入长度，可能使本来指数时间的算法”看起来”像多项式时间。
  • 图的编码：邻接表 vs 邻接矩阵，两者之间只差多项式因子。

Examples of problems in P

PATH

\[\text{PATH} = \{ \langle G, s, t \rangle \mid G \text{ is a directed graph with a directed path from } s \text{ to } t \}.\]

Theorem: PATH \(\in \mathrm{P}\).

Proof:

We construct a polynomial-time algorithm \(M\) that decides PATH:

\(M\) = “On input \(\langle G, s, t \rangle\), where \(G\) is a directed graph with nodes \(s\) and \(t\):

  1. Place a mark on node \(s\).
  2. Repeat the following until no additional nodes are marked:
    • Scan all edges of \(G\). If an edge \((a, b)\) is found where \(a\) is marked and \(b\) is not, mark \(b\).
  3. If \(t\) is marked, accept. Otherwise, reject.”

Complexity Analysis:

  • Let \(n = |V|\) (number of vertices) and \(m = |E|\) (number of edges).
  • Step 2 repeats at most \(n\) times (each iteration marks at least one new node).
  • Each iteration scans all \(m\) edges, taking \(O(m)\) time.
  • Total time: \(O(n \cdot m) = O(n^3)\) (since \(m \leq n^2\)).

Therefore, PATH \(\in \mathrm{P}\). \(\square\)

RELPRIME

\[\text{RELPRIME} = \{ \langle x, y \rangle \mid x, y \text{ relatively prime} \}.\]

Theorem: RELPRIME \(\in \mathrm{P}\).

Proof:

We use the Euclidean algorithm to compute the greatest common divisor (gcd).

Algorithm E (Euclidean Algorithm) on input \(\langle x, y \rangle\):

  1. Repeat while \(y \neq 0\):
    • Let \(x \leftarrow x \bmod y\).
    • Swap \(x\) and \(y\).
  2. Output \(x\) as \(\gcd(x, y)\).

Algorithm R on input \(\langle x, y \rangle\):

  1. Run E to obtain \(d = \gcd(x, y)\).
  2. If \(d = 1\), accept. Otherwise, reject.

Complexity Analysis:

  • After each iteration where \(x \leftarrow x \bmod y\), the new value of \(x\) is at most half of the old value (when \(y \leq x\)).
  • Therefore, the algorithm requires at most \(O(\log x + \log y)\) iterations.
  • Each iteration involves arithmetic operations (addition, subtraction, modulo) that run in polynomial time with respect to the binary representation length.
  • Total time: polynomial in the input size.

Therefore, RELPRIME \(\in \mathrm{P}\). \(\square\)

Every context-free language is in P

Theorem: Every context-free language is in P.

  • Every context-free language \(L\) has an equivalent Chomsky Normal Form context-free grammar \(G'\) such that \(L(G') = L\).
  • The CYK algorithm can determine whether \(w \in L\) or not in \(O(n^3)\) time (where \(n = |w|\)).

Therefore, Every context-free language is in P.

Let \(L\) be an arbitrary context-free language. We need to show that there exists a deterministic Turing machine that decides membership in \(L\) in polynomial time.

Step 1: Convert to Chomsky Normal Form

By the Chomsky Normal Form theorem, every context-free grammar \(G\) can be transformed into an equivalent grammar \(G'\) in Chomsky Normal Form such that \(L(G') = L(G) = L\).

In Chomsky Normal Form, every production rule has one of two forms: - \(A \to BC\) (where \(A, B, C\) are variables) - \(A \to a\) (where \(A\) is a variable and \(a\) is a terminal)

Step 2: Apply the CYK Algorithm

The Cocke-Younger-Kasami (CYK) algorithm is a dynamic programming algorithm that decides whether a string \(w\) of length \(n\) belongs to \(L(G')\).

CYK Algorithm on input \(w = w_1w_2\ldots w_n\):

  1. For \(i = 1\) to \(n\):
    • Set \(V_{i,1} = \{A \mid A \to w_i \text{ is a production in } G'\}\)
  2. For \(j = 2\) to \(n\):
    • For \(i = 1\) to \(n-j+1\):
      • Set \(V_{i,j} = \emptyset\)
      • For \(k = 1\) to \(j-1\):
        • For each production \(A \to BC\) in \(G'\):
          • If \(B \in V_{i,k}\) and \(C \in V_{i+k,j-k}\):
            • Add \(A\) to \(V_{i,j}\)
  3. Accept if and only if the start variable \(S \in V_{1,n}\)

Complexity Analysis:

  • There are \(O(n^2)\) subproblems (each table entry \(V_{i,j}\))
  • For each subproblem \(V_{i,j}\), we consider \(O(j)\) possible splits
  • For each split, we check all productions \(A \to BC\) (let \(|P|\) be the number of such productions)
  • Total time: \(O(n^3 \cdot |P|)\)

Since \(|P|\) is a constant depending only on the grammar \(G'\) and not on the input string length \(n\), the algorithm runs in \(O(n^3)\) time.

Conclusion:

The CYK algorithm decides membership in \(L\) in polynomial time (\(O(n^3)\)) for any context-free language \(L\). Therefore, every context-free language is in P. \(\square\)

Class NP

验证器与 NP 类

Verifier and Certificate

NoteDefinition: Verifier

A verifier \(V\) for a language \(A\) is an algorithm such that \[w \in A \iff \exists c \; V(\langle w, c \rangle) \text{ accepts}.\] If \(V\) runs in polynomial time in \(|w|\), we say \(A\) is polynomially verifiable. The string \(c\) is called a certificate (or witness).

对于多项式时间验证器，certificate 的长度至多是 \(|w|\) 的多项式。

\[\mathrm{COMPOSITES} = \{ x \in \mathbb{N} \mid x = pq \text{ for some } p, q > 1 \}\]

\(\mathrm{COMPOSITES} \in \mathrm{NP}\)：certificate 是 \(x\) 的一个因子 \(p\)（\(1 < p < x\)）。验证器检查 \(p \mid x\) 且 \(1 < p < x\)，多项式时间。

实际上 Agrawal–Kayal–Saxena (2002) 证明了 \(\mathrm{COMPOSITES} \in P\)（即 \(\mathrm{PRIMES} \in P\)），但这是一个非平凡的结果。

NP: Two Equivalent Definitions

NoteDefinition: NP

\[\mathrm{NP} = \{ A \mid A \text{ has a polynomial-time verifier} \}.\]

Theorem: A language is in NP if and only if it is decided by some nondeterministic polynomial-time TM.

Direction 1 (Verifier \(\Rightarrow\) NTM)：

设 \(V\) 在 \(n^k\) 时间内验证 \(A\)。构造 NTM \(N\)：

\(N\) on input \(w\)（\(|w| = n\)）：

  1. 非确定性地猜一个长度至多 \(n^k\) 的 certificate \(c\)。
  2. 运行 \(V\) on \(\langle w, c \rangle\)。
  3. 若 \(V\) 接受则接受，否则拒绝。

若 \(w \in A\)，则存在某个 \(c\) 使 \(V\) 接受，从而 \(N\) 在某条分支上接受。

Direction 2 (NTM \(\Rightarrow\) Verifier)：

设 NTM \(N\) 在多项式时间判定 \(A\)。构造验证器 \(V\)：

\(V\) on input \(\langle w, c \rangle\)：

  1. 将 \(c\) 解读为 \(N\) 每步的非确定性选择序列。
  2. 按 \(c\) 的指示模拟 \(N\) 的一条分支。
  3. 若该分支接受则接受，否则拒绝。

\(\square\)

NP 可以看成”多项式时间可验证”的问题类，也可以看成”非确定性多项式时间可决定”的问题类，两种视角等价。

Examples in NP

HAMPATH

\[\mathrm{HAMPATH} = \{ \langle G, s, t \rangle \mid G \text{ 有一条从 } s \text{ 到 } t \text{ 的 Hamiltonian path} \}\]

Hamiltonian path 是恰好经过图中每个节点一次的路径。

  • Certificate：一条节点序列 \(v_1, \dots, v_n\)，\(v_1 = s\)，\(v_n = t\)。
  • Verifier（多项式时间）：检查路径长度 = 节点数、起终点正确、每对相邻节点间有边、所有节点互不相同。

\(\mathrm{HAMPATH} \in \mathrm{NP}\)。目前不知是否在 P 中。

CLIQUE

\[\mathrm{CLIQUE} = \{\langle G, k \rangle \mid G \text{ 是无向图且含有大小为 } k \text{ 的 clique}\}\]

Clique 是一个完全子图，其中任意两点间都有边。

  • Certificate：\(k\) 个节点的集合 \(c\)。
  • Verifier \(V\) on \(\langle \langle G, k \rangle, c \rangle\)：
    1. 检查 \(c\) 是否恰有 \(k\) 个不同节点。
    2. 检查 \(c\) 中任意两点间是否都有边。
    3. 全部满足则接受。
  • NTM 视角：非确定性地选一个大小 \(k\) 的节点集，检查是否构成 clique。

SUBSET-SUM

\[\mathrm{SUBSET\text{-}SUM} = \{ \langle S, t \rangle \mid S = \{x_1, \dots, x_k\},\; \exists \{y_1, \dots, y_\ell\} \subseteq S,\; \sum_i y_i = t \}\]

  • Certificate：选出的子集，用长 \(k\) 的 0/1 向量编码。
  • Verifier：计算子集和，检查是否等于 \(t\)，多项式时间。

\(\mathrm{SUBSET\text{-}SUM} \in \mathrm{NP}\)（事实上是 NP-complete，见下一章）。

P vs NP

  • P：能在多项式时间内判定的语言类
  • NP：能在多项式时间内验证的语言类

\[\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}\]

核心开放问题：\(\mathrm{P} \stackrel{?}{=} \mathrm{NP}\)。多数研究者相信 \(\mathrm{P} \ne \mathrm{NP}\)，但目前没有严格证明。已知 \(\mathrm{NPSPACE} = \mathrm{PSPACE}\)（Savitch 定理），其余包含关系是否严格仍是猜测。

flowchart TB
    subgraph EXPTIME_box["EXPTIME"]
        subgraph PSPACE_box["PSPACE = NPSPACE"]
            subgraph NP_box["NP"]
                subgraph P_box["P"]
                end
            end
            subgraph coNP_box["coNP"]
            end
        end
    end

Extensions: PH, BPP, PP

PH (Polynomial Hierarchy)

NoteDefinition: Polynomial Hierarchy

\(\mathrm{PH}\) 是 NP 和 coNP 的自然推广，对应多重交替量词。

  • \(\Sigma_0^P = \Pi_0^P = \mathrm{P}\)
  • \(\Sigma_1^P = \mathrm{NP}\)（\(\exists\)），\(\Pi_1^P = \mathrm{coNP}\)（\(\forall\)）
  • \(\Sigma_k^P\)：\(L = \{ x \mid \exists y_1 \forall y_2 \exists y_3 \dots Q_k y_k,\; R(x, y_1, \dots, y_k) \}\)，\(R\) 多项式时间可判定
  • \(\Pi_k^P\)：以 \(\forall\) 开始

\[\mathrm{PH} = \bigcup_{k \ge 0} \Sigma_k^P\]

Oracle 定义：\(\Sigma_1^P = \mathrm{NP}\)，\(\Sigma_{k+1}^P = \mathrm{NP}^{\Sigma_k^P}\)，\(\Pi_{k+1}^P = \mathrm{coNP}^{\Sigma_k^P}\)。例如 \(\Sigma_2^P = \mathrm{NP}^{\mathrm{NP}}\)，即有 SAT oracle 的 NTM 在多项式时间能解的问题。

性质：

  • Inclusion：\(\Sigma_k^P \subseteq \Sigma_{k+1}^P\)，\(\Pi_k^P \subseteq \Pi_{k+1}^P\)
  • Collapse：若 \(\Sigma_k^P = \Pi_k^P\)，则 PH 塌缩到第 \(k\) 层。特别地，\(\mathrm{P} = \mathrm{NP}\) \(\Rightarrow\) \(\mathrm{PH} = \mathrm{P}\)。
  • Complete Problems：第 \(k\) 层有对应的完备问题（\(k\) 层交替量词的 QSAT 变种）。

BPP (Bounded-error Probabilistic Polynomial Time)

NoteDefinition: BPP

\(L \in \mathrm{BPP}\) iff 存在概率图灵机 \(M\)：

  1. \(M\) 在所有输入上多项式时间运行。
  2. \(x \in L \Rightarrow \Pr[M(x) \text{ accepts}] \ge 2/3\).
  3. \(x \notin L \Rightarrow \Pr[M(x) \text{ accepts}] \le 1/3\).

\(2/3\) 和 \(1/3\) 不是固定的——只要与 \(1/2\) 有 inverse polynomial gap，通过Amplification（重复运行取多数票）可将错误概率降到 \(2^{-n}\)。

与其他类的关系：

  • \(\mathrm{P} \subseteq \mathrm{BPP}\)
  • \(\mathrm{BPP} \subseteq \Sigma_2^P \cap \Pi_2^P\)（Sipser-Gacs-Lautemann Theorem）
  • 普遍猜想 \(\mathrm{P} = \mathrm{BPP}\)（Derandomization 猜想：随机性不能显著增强计算能力）

PP (Probabilistic Polynomial Time)

NoteDefinition: PP

\(L \in \mathrm{PP}\) iff 存在概率图灵机 \(M\)：

  1. \(M\) 在所有输入上多项式时间运行。
  2. \(x \in L \Rightarrow \Pr[M(x) \text{ accepts}] > 1/2\).
  3. \(x \notin L \Rightarrow \Pr[M(x) \text{ accepts}] \le 1/2\).

PP 与 BPP 的关键区别：PP 不要求错误概率远离 \(1/2\)。接受概率可能只比 \(1/2\) 大 \(2^{-n}\)，无法通过少量重复来有效区分——需要指数级重复次数。

PP 的计算能力很强：

  • \(\mathrm{NP} \subseteq \mathrm{PP}\)（PP 可解 MAJ-SAT：满足赋值是否超过一半）
  • Toda’s Theorem：\(\mathrm{PH} \subseteq \mathrm{P}^{\mathrm{PP}}\)，即 PP 的能力至少与整个多项式层级相当。