复杂度理论 ¶

Proof. 任意 CFL \(A\)，存在一个 CFG \(G=(V, \Sigma, R, S)\) 生成 \(A\) 且是 CNF 的。（说明任意一个字符串 \(w\in A\)，需要在 \(2|w| - 1\) 步内生成）

但枚举所有长度为 \(2|w|-1\) 的字符串需要 \(|R|^{2|w|-1}\) 复杂度，非多项式。所以要通过 dp 来实现，假设 \(w=a_1\cdots a_n\)，问是否有 \(S\Rightarrow^* w\)。

• 对于 \(1\leq i\leq j\leq n\)，定义 \(T[i, j] = \{A\in V-\Sigma: A\Rightarrow a_ia_{i+1}\cdots a_j\}\)
• Goal：是否有 \(S\in T[1, n]\)
• Base case：对于 \(1\leq i\leq n\)，有 \(T[i, i] = \{A\in V-\Sigma: (A, a_i)\in R\}\)
• Recurrence：对于 \(1\leq i\leq j\leq n\)，有 \(T[i, j] = \bigcup_{k=i}^{j-1}\{A\rightarrow BC: B\Rightarrow^* a_i\cdots a_k\land C\Rightarrow^* a_{k+1}\cdots a_j\}\)
  • 即 \(T[i, j] = \bigcup_{k=i}^{j-1}\{B\in T[i, k]\land C\in T[k+1, j]\}\)

子问题数量为 \(\dfrac{n^2}{2}\)，每个子问题需要消耗 \(n\cdot |R|\) 时间，总共需要 \(O(n^3|R|)=O(n^3)\) 时间，是多项式。

Proof. 左推右，存在多项式时间的 verifier \(V\)，需要构建一个 NTM \(M\) 在多项式时间内判定 \(A\)。构造 \(M\) = on input \(\mathtt{"}x\mathtt{"}\):

1. non-deterministically generate a certificate \(y\) with \(|y|\leq\mathrm{poly}(|x|)\)
2. run \(V\) on input \(\mathtt{"}x\mathtt{"}\mathtt{"}y\mathtt{"}\)
3. if \(V\) accepts \(\mathtt{"}x\mathtt{"}\mathtt{"}y\mathtt{"}\)
4.   accepts \(\mathtt{"}x\mathtt{"}\)
5. else
6.   rejects \(\mathtt{"}x\mathtt{"}\)

右推左，存在一个 NTM \(M\) 多项式时间内判定 \(A\)，需要构造一个多项式时间 verifier \(V\)。构造 \(V\) = on input \(\mathtt{"}x\mathtt{"}\mathtt{"}y\mathtt{"}\):

1. run \(M\) on \(\mathtt{"}x\mathtt{"}\) deterministically under the guidance of \(y\)
2. if \(M\) accepts \(\mathtt{"}x\mathtt{"}\)
3.   accepts \(\mathtt{"}x\mathtt{"}\mathtt{"}y\mathtt{"}\)
4. else
5.   rejects \(\mathtt{"}x\mathtt{"}\mathtt{"}y\mathtt{"}\)

\(x\to f(x)\)，再判定 \(f(x)\in B\) 即可，转化时间 \(\mathrm{poly}(|x|)\)，判定时间 \(\mathrm{poly}(|f(x)|)\)，且有 \(|f(x)|\leq\mathrm{poly}(|x|)\)，所以总时间也是多项式时间。

Proof. 令 \(A\) 是任意一个属于 NP 的语言。需要证明 \(A\leq_P\mathrm{SAT}\)。

存在一个 NTM \(N\) 在 \(n^k\) 时间内判定 \(A\)。判定 \(a_1\cdots a_n\in A\) 等价于存在一个分支 \((s, \rhd\underline{⌴}a_1\cdots a_n)\vdash_M(q_1, \rhd u_1\underline{a_1}v_1)\vdash_M\cdots\vdash_M(y, \rhd u\underline{a}v)\)，可以写成 \(\rhd⌴sa_1\cdots a_n\vdash_M\rhd u_1a_1q_1v_1\vdash_M\cdots\vdash_M\rhd uayv\)，其中最多有 \(n^k\) 个 configurations，并且每个 configuaration 对应字符串的长度最长 \(n^k\)。

建立一个 \(n^k\times n^k\) 的表，表中每个格子可以填状态或者 symbol，是否存在这样的转换即能否找到一种正确的填表方式。

• 对于 \(1\leq i\leq n^k,\ 1\leq j\leq n^k, c\in K\cup\Sigma\)，\(x_{ijc}\) 表示这个位置上是否填了 \(c\)
• 需要满足：
  • 对于每一个 \(i, j\)，要有 \(\displaystyle\sum_{c\in k\cup\Sigma}x_{ijc}\geq 1\)，即 \(\displaystyle\bigvee_{c\in K\cup\Sigma}x_{ijc}\) 为真
  • 对于每一个 \(i, j\)，要保证一格内只能有一个符号，即 \(\displaystyle\bigwedge_{c\neq c'}\overline{x_{ijc}\land x_{ijc'}}=\bigwedge_{c\neq c'}(\overline{x_{ijc}}\lor\overline{x_{ijc'}})\) 为真
  • \(x_{11\rhd}\land x_{12⌴}\land x_{13s}\land \cdots\) 为真（规定初始行）
  • 要保证后一行是前一行一步操作到的
    • 用 2*3 的框进行检查，合法的这样的框有 \(|K\cup\Sigma|^6\) 种
  • 存在接受状态，\(\displaystyle\bigvee_{i, j}x_{ijy}\) 为真

Proof. \(\forall L'\in NP\), \(L\leq_P A\)，因为 \(A\leq_P B\)，所以 \(L\leq_P B\)。

空间上，对于任意 \(f\colon\mathbb{N}\to\mathbb{N}\)（满足一些性质），都存在一个语言 \(A\) 满足：

1. \(A\) 可以被 DTM 在 \(O(f(n))\) 空间内判定
2. \(A\) 不能被 DTM 在 \(o(f(n))\) 空间内判定
   • 大 \(O\) 小于等于，小 \(o\) 小于，即至少需要 \(f(n)\) 空间）

时间上，对于任意 \(f\colon\mathbb{N}\to\mathbb{N}\)（满足一些性质），都存在一个语言 \(A\) 满足：

1. \(A\) 可以被 DTM 在 \(O(f(n))\) 时间内判定
2. \(A\) 不能被 DTM 在 \(o(\dfrac{f(n)}{\log f(n)})\) 时间内判定
   • 时间的 hierarchy theorem 要弱一点，提高 \(\log f(n)\) 才能多判定问题