好好的一门专业课TCS怎么一点时间都没花

\def\set{\Set} $\def\set{\Set}$

\def \sube{\subseteq}$\def \sube{\subseteq}$

\def \sub{\subset}$\def \sub{\subset}$

\def \and{\wedge} $\def \and{\wedge}$

\def \or{\vee} $\def \or{\vee}$

完蛋了，感觉真要挂科了，这学期活得像个傻逼。

球球了，能不能不要挂科啊。

update1/14：虽然六十多但是没挂科，虽然绩点没了但是至少没挂科……

Slide 1 (virginia.edu) Theory of Computation (virginia.edu)

-/@ Computational Complexity A Modern Approach.pdf at main · EMOAIRX/- (github.com)

• 一个语言是可判定的，当且仅当该语言和该语言的补集都是图灵可识别的。

  $$正则 \sub 上下文无关 \sub 可判定 \sub 图灵可识别$$

• 二教316考试

复杂性类

• $$\rm L \sube NL \sube NC \sube P \sube NP \cap coNP \sube NP \cup coNP\sube PH\\ \rm PH\sube PSPACE \sube EXP \sube EXPSPACE\\ \\ \rm P \sube P/poly\\ \rm NC^1\sube L \sube NL \sube NC^2 \sube NC\sube P \\ \\ \rm NSPACE(f(n))\sube SPACE(f^2(n))\\ \rm PSPACE = NPSPACE\\ \rm NSPACE(f(n)) = coNSPACE(f(n)),f(n)\ge \log n\\ \rm NL=coNL(\overline{PATH}\in NL)\\ \\ \rm SAT:NP-C\\ \rm PATH:NL-C\\ \rm TAUT:coNP-C\\ \rm CIRCUIT\_VALUE:P-C\\ \rm TQBF:PSPACE-C\\ \rm EQ_{REX \uparrow}:EXPSPACE-C$$

• 递归定理：你可以递归

归约

• 泵引理，正则语言版：

  • 存在常数 p，如果 $s \in A , |s| \ge p$ 则 $s = xyz$ 满足以下条件
  • $\forall i \ge 0,xy^iz \in A$
  • $|y| > 0$
  • $|xy| \le p$

• 下推自动机PDA 与 CFG 等价，这个语言是CFL。

• 泵引理，上下文无关语言版
  • 存在常数 p，如果 $s \in A , |s| \ge p$ 则 $s=uvxyz$，满足
  • $\forall i \ge 0,uv^ixy^iz \in A$
  • $|vy| > 0$
  • $|vxy| \le p$

时间复杂性

• $TIME(t(n)) = {L \mid 某个O(t(n))时间的\underline{单带}DTM判定语言L }$
• 时间复杂性与模型有关，单带与多带是平方关系，非确定性和确定性是指数关系。
• 定理7.8 设函数 $t(n) \ge n$ ，则每个 $t(n)$ 时间多带 $TM$ 都与某个 $O(t^2(n))$ 时间单带 $TM$ 等价。
  • 每个带子活跃部分长度是 $t(n)$，模拟一次移动也就是 $O(t(n))$ 步的。（不够了扩展）
• 定理7.10 ，设函数 $t(n)\ge n$, 则每个 $t(n)$ 时间 单带NTM都与某个$2^O(t(n))$时间单带DTM 等价
  • 模拟每个分支，$b^{t(n)}$ 个分支，b是所有节点做大分支数。
• P类 $\rm P = \cup_kTIME(n^k)$。
• $\rm PATH = {(G,s,t)\mid 有向图G有从s到t的有向路径}$
• 定理7.12 $\rm PATH \in P$
• $\rm RELPRIME = {(x,y) \mid x与y互素}$
• 定理7.13 $\rm RELPRIME \in P$

• 定理7.14 若 $\rm L$ 是 $\rm CFL$ ，则 $\rm L \in P$。

  • 上下文无关语言，可以用动态规划算法
• $\rm NP = \set{L\mid 语言L有多项时间验证机}$
  • $A=\set{w\mid \exist 字符串c，算法V接受 \left}$
    • 算法V是验证机，c为w是A的成员的资格证书。
  • 如果是多项式时间验证机，要求 $|c|$ 是 $|w|$ 的多项式（短证明），在$|w|$ 的多项式时间内运行（容易验证）。
  • 也等价于非确定性多项式时间判定。
    • 证明：如果是属于NP的，也就是有验证机，通过验证机构造判定机，通过非确定性选择 $c$。
    • 如果是有NTM判定机的，把每个符号看成是非确定性的描述。
  • $\rm NTIME(t(n)) = \set{L \mid 某个 O(t(n))时间NTM判定语言L}$
  • $\rm NP = \cup_k NTIME(n^k)$

• $\rm HAMPATH = {(G,S,T)\mid (有向)图G包含从s到t的哈密顿路径} \in NP$

  • 搜索可以规约为判定
  • 其补不清楚

• $\rm COMPOSITES = \set{ x | x=pq, 整数p,q>1} \in NP$

• $\rm PRIMES \in NP$，不知道，不知道，是对的，AKS也说是对的，但是不知道不会做啊啊啊
• $\rm CLIQUE = \set{(G,k) \mid 无向图 G 有K_k子图，即k-团} \in NP$
• $\rm SUBSET-SUM = \set{(S,t) \mid 存在S的一个子集的和为t} \in NP$

• $\rm P \sube NP \cap coNP$

• P与NP问题

  • P=成员资格可以快速判定
  • NP=成员资格可以快速验证
  • $\rm P\sube NP \sube EXP$

• 多项式时间 m 归约：

  • $\rm A \le_m^p B\ via\ f$ 说明
    • $x \in A$ 与 $\rm f(x) \in B$ 等价，
    • f 是多项式时间可计算函数。
  • 满足传递性，P 对归约其满足封闭性，NP 对归约封闭

• $\rm SAT$ 给定布尔公式，确定这个公式是否可满足。

  • $\rm cnf$合取范式指的是子句（文字的析取 $\or$） 的合取 $\and$
  • $\rm cnfSAT \le_m^p 3SAT$
    • 通过增加变元，使得前后两个公式同时可满足或同时不可满足。
    • $a1\or a2\or a3\or a4\Rightarrow(a1\or a2\or z)\and(\neg z\or a3 \or a4)$
  • $\rm 3SAT$ 是可满足的三元合取范式。

• $\rm 3SAT \le_m^p CLIQUE$

  • 证明思路是把一个公式转化为一个图和一个数
  • 对于两个子句不矛盾的就可以连起来，如果有一个团说明每个子句都可以两两不矛盾。
  • 证明正确性是双向的。同时要证明复杂性

• 库克定理 任何NP语言都多项式时间归 约到cnf-SAT

  • 任何单带图灵机的判定过程都可以看作是上下一个2*3的格子发生了变化，只有一部分是合法窗口。
  • 构造方法为：
    • 利用 $X_{i,,j,k}$ 表示 $i,j$ 这个各自是不是 $k$。
    • 每个单元恰好包含一个符号。
    • 第一行为初始格局。
    • 下一行是上一行的合法转移。也就是每个窗口都是合法的，
    • 某一行是接受格局。
  • 这个归约是多项式的。$\phi$ 的二进制串长度为 $O(n^{2k} \log n)$。

• NP完全，NP难

  • 若 NP 中的每个语言 A 都多项式时间归约到B，则B是NP难的。
  • 若 B 是 NP 难的并且 B 属于NP，则 B 是 NP 完全的。
  • 若 B 是 NP 完全的，B 多项式时间归约到 C，C 属于 NP，则 C 是 NP 完全的。

• 几个 NP 完全问题

  • $\rm VERTEXCOVER={(G,k)|无向图G有k 个顶点的顶点覆盖}$
    • 根据选不选这个放0还是1，剩下的用三角阵。
  • $\rm HMAPATH$
    • 从左往右走是选1，从右往左走是选0
  • $\rm SUBSETSUM$
    • 搞一个选 $x_1=1,x_1=0$ 的几个子句是什么。增加一些补充的凑数的变量。

• 按照可近似性分类

  • 完全多项式时间近似方案FPTAS，关于n和$1/\epsilon$ 的多项式
  • 多项式时间近似方案PTAS，关于 $n^{f(1/\epsilon)}$ 的多项式。
  • 常数近似比APX
  • 对数近似比log-APX
  • 多项式近似比poly-APX

空间复杂性

• 设 DTM M在所有输入上都停机. 设M在长度为n的输入上最多扫描 f(n)个不同带方 格, 则M的空间复杂性是f(n).
• 设 NTM M在所有输入的所有计算分支上都停机，设M在长度为 $n$ 的输入上在任何计算分支上最多扫描 $f(n)$ 个不同带方格, 则M的空间复杂性是 $f(n)$。
• $\rm SPACE(f(n)) = \set{ L | 语言L被O(f(n))空间DTM判定 }$
• $\rm NSPACE(f(n)) = \set{ L | 语言L被O(f(n))空间NTM判定 }$
• $\rm SAT \in SPACE(O(n))$
• $\rm ALL_{NFA}^c \in NSPACE(O(n))$
  • 猜测拒绝的串，用非确定性线性空间追踪NFA状态。（如果某个时刻所有标记都不落在接受状态上，则接受；否则拒绝。
    • 所有标记的不同位置组合共有 $2^q$ 种，$q$ 是状态数，存放所有标记需要 $O(q)$ 的空间 $q\le n$，总空间是 $O(n)$。

• 已知 $\rm NTIME(f(n)) \sube TIME(2^{O(f(n))})$

  • 用确定型时间来模拟非确定型时间，要有指数的增长。
  • 所以 $\rm NP \sube EXP = EXPTIME$

• Savitch定理：$\rm NSPACE(f(n)) \sube SPACE(f^2(n))$

  • 用确定型来模拟非确定型空间，只有平方的增长。
  • 推理得到 $\rm NPSPACE=PSPACE$。

  • 证明思路是：

    1. 由于最多只有 $f(n)$ 的空间，也就是 $f(n)$ 的格局大小，所以不同的数量是 $2^{O(f(n))}$ ，可以运行 $2^{O(f(n))}$ 步。这样就知道

       • $\rm NSPACE(f(n)) \sube NTIME(2^{O(f(n))})$

    2. 利用 $\rm CANYIELD(c_1,c_2,t)$ 表示格局 $c_1$ 能否在 $t$ 步内到达格局 $c_2$。

       • 这玩意儿可以二分，只需要存一个空间为 $O(f(n))$ 的中间格局 $c_m$。
       • 运行 $\rm(c_1,c_m,[t/2]),(c_m,c_2,t-[t/2])$ 。全部枚举一遍。递归深度为 $O(f(n))$，每次需要把一个 $O(f(n))$ 的入栈。

• 所以我们知道了 $\rm PSPACE = NPSPACE$

  • $\rm P \sube NP \sube PSPACE \sube EXP,P\not= EXP$

• 归约

• 两个复杂性类 $\rm A\sube B$。定义归约 $\le_m^A$，满足传递性，并且AB两者都封闭。

  • $A=B \iff 某个B完全问题 \in A \iff 所有B完全问题 \in A$
  • $A\not=B \iff 所有B完全问题 \not \in A$

• 复杂性类，完全问题

• 分离(separate)： 常常借助于下界

• 塌方(collapse)： 常常借助于模拟

• 上界：完成一个任务，有多少资源就足够了；下界：至少要多少资源。

• PSPACE完全

  • 多项式时间归约
    • 例如 $\phi=\forall x \exist y[(x\or y)\and(\neg x \or \neg y)]$
    • 全称带量词布尔公式（不包括自由变元）
  • $\rm TQBF=\set{(\phi)\mid \phi 是真的tqbf}$
  • 定理8.8： $\rm TQBF 是 PSPACE 完全的$
    • 证明思路是用递归算法，把画面分成两半。
      1. 证明是PSPACE的，通过递归代入。
      2. 证明别的被DTM判定的语言，利用PSPACE空间的，都能构造出一个 $\phi$。
    • 方法就是走一步可以，走多步就对半开，$\exist m_1 \forall(c_3,c_4) \in \set{(c_1,m_1),(m_1,c_2)}[\phi(c_3,c_4,t/2)]$ 。
    • $((c_3=c_1 \and c_4=m_1) \or (c_3=m_1 \and c_4=c_2)) \and (…)$
    • 选择常数 $d$ 使得 $M$ 在长度为 $n$ 的输入上不同的格局总数不超过 $2^{df(n)}$。
    • 具体递归的时候，记录 $m_1$ 需要 $f(n)$，记录往哪个方向选需要 $1$，最多递归 $O(f(n))$ 次。

• 公式博弈：

  • 一个人选存在，也就是尽可能为真。一个人选所有，也就是尽可能为假。其实就是 TQBF
  • $\rm FORMULA\ GAME=\set{(\phi) \mid 在关于 \phi 的公式博弈中选手 E 有必胜策略}$

• 广义地理学游戏：

  • 每次可以选一个顶点走，不能扩展的人失败。
  • $\rm GG=\set{(G,b)\mid 在图G中b点开始的广义地理学游戏中先手有必胜策略}$
  • 是PSPACE完全的，可以拿公式博弈来归约。首先证明PSPACE，模拟即可。其次是用把一个存在任意的公式转化为一个地理游戏。具体方法是先让每个人选，然后考虑合取范式，就是先手要存在真。所以让后手先选一个子句，然后先手选一个变元，这时候如果后手不能选了的话说明先手胜，也就是所有子句都不可能有假。

• 亚线性空间：一条输入带只读，不计入复杂性，一条输入带可读写考虑复杂性。

• $\rm L=SPACE(\log n),NL = NSPACE(\log n)$，考虑 $\log n$ 是为了考虑稳健性和丰富性。

• $\rm PATH \in NL$，因为搜索的时候可以存一个节点的编号，也可以选择下一个节点。

  • $\rm NSPACE(f) \sube SPACE(f^2)$，条件为 $f(n) \ge \log n$

• 关于 $NL$ 完全问题，这时候多项式时间归约不太靠谱，要用 对数空间归约。对数空间规约满足传递性。

  • $\rm PATH$ 是 $\rm NL$ 完全的，对数空间 NTM 格局的长度是 $O(\log n)$。所以可以枚举所有串判断是否是合法格局，也可以枚举所有格局对判断是否可以是边。所需要的工作空间是 $O(\log n)$
  • 由于 $\rm PATH \in P$ ，所以 $\rm NL \sube P$

• 确定型复杂性类显然对补封闭。对非确定性有点问题。

  • 不知道 $\rm NP=? coNP$，但是 $\rm NSPACE(f(n))=coNSPACE(f(n)),f(n)\ge \log n$
  • 这里关于 $\rm NL = coNL$ 的方法是 $\rm PATH^c \in NL$
    • 方法是如果知道能访问到的点的个数，那么枚举的距离不会超过点的个数。
    • 关于怎么计算有多少个距离不超过 $k$ 的点，因为我们可以求出来距离恰好为 $k$ 的点有多少个。
    • 其实就是枚举一个长度，然后对于每个点 $v$ 判断是否距离不超过 $i$，换言之 $s$ 出发走距离不超过 $i-1$ 步能先到达一个点 $u$ ，然后看 $(u,v)$ 是否可以作为一条边。
    • 算出来有这么多个点之后，如果和之前的相等说明就这么多。

交错式

lect06.pdf (harvard.edu)

这门课好棒啊呜呜呜

• 交错式图灵机(ATM)是一种NTM，计算树中的非确定性分支点包括全称(universal)和存在(existential)两类，一个全称分支点接受当且仅当它的所有儿子接受，存在就是一个儿子接受。由此定义 $\Sigma_i$ 型 ATM和 $\Pi_i$ 型ATM，$\Sigma_0$ 就是根节点为存在。最多有 $i-1$ 次交错。
• 可以定义交错式时间与空间类
• $\rm ATIME(t(n)) = \set{L(M)\mid M是O(t(n))时间 ATM}$
• $\rm ASPACE(f(n)) , AP , APSPACE, AL…$
• $\rm NP \cup coNP \sube AP$
  • 完蛋了咋证明啊
• $\rm TAUT = \set{(\phi)\mid \phi为永真式} \in AP$
  • 对于所有输入 $(\phi)$ ，全称地选择所有变元并赋值，对于一个具体地赋值计算，如果存在则接受。
  • TAUT补是NP的，因为给一个证据就能证明存在不是永真的。TAUT是NP完全的，因为SAT可以归约到TAUP，判断是否可满足，只要加一些存在就可以。
  • TAUT是NP完全的，TAUT补是NP的，那么任何一个coNP的语言A，A补是NP的，A补能归约到TAUT，$x\in \bar A \iff f(x) \in L$，同时取补可以发现 A能归约到TAUT补，所以TAUT是补NP完全的。
• $\rm MIN\ FORMULA=\set{(\phi)\mid \phi是极小布尔公式} \in AP$
  • 方法是，全称地选择所有比 $\phi$ 短的公式，然后存在性地选一组变元地赋值，如果存在不同则接受，否则拒接。
• 定理10.19 设 $f(n) \ge n$ 则
  • $\rm ATIME(f(n)) \sube SPACE(f(n)) \sube ATIME(f^2(n))$
  • $\rm L \sube P=AL \sube PSPACE=AP \sube EXP=APSPACE$
  • 证明 lect06.pdf (harvard.edu)
  • 还得是国外的讲义啊。

• 引理10.20：$f(n)\ge n,\rm ATIME(f(n))\sube SPACE(f(n))$

  • 考虑递归整个计算树，这样是平方的，但是格局不需要记录下来，只需要记录沿路径的非确定性选择（？）

• 引理10.12： $f(n)\ge n,\rm SPACE(f(n)) \sube ATIME(f^2(n))$

  • 用 $\rm CANYIELD(c_s,c_a,2^{O(f(n))})$，存在地分支，每个分支猜一个 $c_m$，然后全称地验证两支。
• 引理10.22： $f(n)\ge \log n,\rm ASPACE(f(n)) \sube TIME(2^{O(f(n))})$
  • 确定型地反向遍历格局图。根据儿子的状态结果推父亲的结果。

• 引理10.23：$f(n) \ge \log n,\rm TIME(2^{O(f(n))}) \sube ASPACE(f(n))$

  • 从接受状态的计算图，从左下方单元开始
  • [a,b,c]
    [-,d,-]
    • 对于单元d, 存在地猜测单元a,b,c的内容，全程地验证三者。
  • 对于第一行直接验证。画面大小为 $2^{O(f(n))} \times 2^{O(f(n))}$，只需要保存单元地指针，只需要 $O(f(n))$。

• 交错式代表一种并行处理能力。

多项式时间层次定理 (PH)

• $\rm \Sigma_iTIME(f(n)) = \set {L \mid L(M),where \ M\ is\ f(n)\ time \Sigma_i\ ATM}$
• $\rm \Pi_iTIME(f(n))$
• 同理定义 $\rm \Sigma_i P,\Pi_i P$
• $\rm PH = \cup_k \Sigma_iP = \cup_k \Pi_i P$
• $\rm PH$ 有一些等价的定义，
  • $\rm ATM:\Sigma_iP,\Pi_iP$
  • $\rm OTM: \Sigma{i+1}P = NP^{\Sigma_iP} , \Pi{i+1}P=coNP^{\Sigma_iP}$
  • 或者用量词+谓词，量词都是多项式有界的。
  • 约定 $\rm \Sigma_0P=\Pi_0P=P$

难解性

• 难解的(intractable) = 不可行的(infeasible) = (outside P) = (hard)
  • 假设难(presumably intractable)，例如NP难，PSPACE难。EXP是可证难解的。EXP是真的难。

空间可构造

• 空间可构造函数是说，$f(n) \ge \log n$ ， $f(n)$ 在 $O(f(n))$ 空间内可计算。也就是存在 TM 以 $f(n)$ 为空间复杂度。

  • space-constructible function

• 线性加速定理 $\rm TIME(cf(n))=TIME(f(n));SPACE(cf(n))=SPACE(f(n))$，通过修改字母表合并相邻格子，合并转移函数即可。

• 对于 $g(n)=o(f(n))$，可以定义 带空间限制的通用机，就是对于输入的图灵机和输入串，对于足够长的输入就控制其运行空间不超过 $f(n)$，对于短的串把答案固化在TM中。同时让运行时间不超过 $2^{f(n)}$。

• Padding引理： 可以padding。识别同一个语言的TM有无穷多个。

• 所以现在可以定义图灵机 $U(M,M10^{n_0})$，然后做一个对角化。

• 对角化之后定义图灵机 B，如果运行图灵机超过 $f(n)$ 空间则拒绝，如果超过步数则拒绝，只有当U拒绝的时候接受，在U接受的时候拒绝。之所以要这个B，是为了引出 空间层次定理

空间层次定理

• 定理9.3 对任何空间可构造函数 $f$, 存在语言A, 在 $O(f)$ 空间可判定, 但不能在 $o(f)$ 空间内判定
  • 设 $A=L(B)$，其中$B$ 是上面所说的对角化用的图灵机。
  • 如果假设 M 在 $g(n)$ 空间内运行。$g(n)=o(f(n))$ ，B 需要 $dg(n)$ 的空间模拟 M。设当 $n | n_0$ 时，$dg(n)<f(n)$，B可以完成对M的模拟，则 $M10^{n_0}$ 在 $L(B)$ 和 $L(M)$ 中不一样，一个接受一个拒绝。这就矛盾了。
• 能有一些推论。

时间

• 时间可构造性就是可以在 $O(t(n))$ 时间内算出 $t(n)$，条件是 $t(n) \ge n \log n$。等价于 存在 TM 以 $t(n)$ 作为时间复杂性。
• 关于带时间限制的通用机一个方法是维护一个计时器。

时间层次定理

• 构造一个语言 $A$，$\rm A \in TIME(O(t(n)))$。证明 $\rm A\not \in TIME(o(t /log t))$
• 方法是对角化，构造图灵机 $B$，并且要求最多只执行 $\rm t(n)/\log t(n)$ 步，每执行一步移动计数器需要 $\log$ 的消耗。所以总的时间不超过 $O(t(n))$，设 $A=L(B)$，则 $A \in \rm TIME(O(t(n)))$。
• 然后考虑 $B$ 是和空间一样的对角化方法，如果 $A=L(M)$ 且 $M$ 可以被 $B$ 模拟，那么 $B$ 可以被 $B$ 模拟，也就是如果 $M10^{n_0}\in L(M)$ 则 $M10^{n_0} \not \in L(B)$，这就导出一个矛盾。
• 总的来说就是存在一个限制为 U 的通用模拟机器，能模拟所有用更少的资源的机器但是输出是对角化的，如果它自己能用更少的资源，那么它自己能模拟自己，但是输出不一样。

推论 $\rm P \subset EXP$

• $\rm EQ_{REX} \in PSPACE$
• $\rm EQ_{REX\uparrow} \not \in P$
• 定理9.15 $\rm EQ_{REX \uparrow}$ 是 EXPSPACE完全的。
  • 证明方法和前面类似，就是说所有的EXPSPACE能搞的语言，也就是有一个计算历史。就是说 $w \in A$ 等价于图灵机 M 在输入 $w$ 上无拒绝计算历史。

相对化

• Oracle Turing Machine
• $\rm P^{SAT} , P^{NP} …$，若 $\rm A$ 是 $\rm D$ 完全的，$\rm C^D = C^A$
• $\rm NP \subseteq P^{SAT} , coNP \subseteq P^{SAT}$
• 非极小化布尔公式 属于 $\rm NP^{SAT}$ ，因为可以非确定性地选择是不是有更短的公式。
• 定理9.19 $\rm \exist A,P^A \sub NP^A;\exist B,P^B = NP^B$
  • 对于 B，设 B=TQBF，则全都是PSAPCE。
  • 对于 A，增量地构造一种语言 A，让 NP^A 包含了 P^A 不包含的内容。
  • 完蛋，这个好难

$\color{red} \text{这里开始基本都是瞎写的内容，也即不适合直接观看，妈的怎么这么摆，感觉挂科也不是不可能啊}$

电路，门

• Boolean Circuit: not,and,or
• Arithmetic Circuit: +-*/,mod,threshold
• 电路族C是无穷个电路，$\rm C=(C_0,C_1…)$ ，其中 $C_n$ 有 n 个输入变量，如果对于每个字符串 $w$ 有 $w \in A \iff C_n(w)=1 , |w| = n$ 则称 $C$ 在 (0,1) 上判定 A。
• 电路的规模是 C 中的门数，短路族的规模复杂度是函数 f(n)=Cn，$\rm SIZE(f(n))$ 是那些有规模为 $f(n)$ 的判定电路构成的集族。
• $\rm P/poly = PSIZE=\cup_kSIZE(n^k)$
• 电路的深度 depth 是输入到输出的最长路径长度。电路族 $\rm (C_0,C_1… C_n…)$ 的深度复杂性是函数 d:N->N, d(n)=Cn。 $\rm DEPTH(f(n))$ 是那些有深度复杂性为 $f(n)$ 的判定电路构成的语言。
• 同样定义了 规模-深度 联合复杂度 $\rm SIZE_DEPTH(s(n),d(n))$
• 例如 $\rm parity_n \in SIZE(O(n))$
• nonuniformity 非一致性
  • 一族电路判定一个语言，$C_n$ 只判定长度为 $n$ 的有穷的输入。电路是非一致性的计算模型。
  • 一个图灵机则判定一个语言，图灵机是一致性的计算模型。
• 所以给图灵机额外信息，称为advice。 lect03.pdf (mit.edu)
• 用电路模拟图灵机：$\rm TIME(t(n)) \sube SIZE(O(t^2(n)))$
  • 每个单元有 $k$ 盏灯代表一个符号，一个单元只能有一盏灯是开着的。
  • 边界上的单元只受上一行两个单元的影响。
• 电路可满足性问题：给定一个布尔电路，确定是否存在某个输入使得这个电路输出1.
• CIRCUIT-SAT是 NP完全 的
• 3-SAT 是 NP完全的的一个证明方法是，用3cnf模拟电路。即把与或非门用3sat来归约。

Karp-Lipton定理

• $\rm NP\sube P/poly \implies PH=\Sigma_2^p$
• 假设PH不塌方，则NP完全问题不能用多项式规模的电路计算。

并行计算

• ATM,NC,PRAM
• PRAM是指共享存储。
• $\rm NC^k$ 是 poly规模，$\rm O(\log ^k n)$ 深度，对数空间一致性条件。
• Nick’s Class，窄电路。 $\rm NC^1 \sube L \sube NL \sube NC^2 \sube NC \sube P$
• $\rm CIRCUIT_VALUE=CVP$，布尔电路C在输入x下输出1。 给定一个布尔电路和一个输入，确定这个电路在这个输入下的输出。
• 这是P完全的。

复杂性理论高级专题

交错式

概率算法

• 【其实参见kyq随机算法】
• 多项式恒等问题，多项式零问题，
• $\rm EQ_{ROBP}$ 问两个只读一次的分支程序是不是等价的。
• 概率图灵机（概率TM），
• PP 多项式运行时间，错误概率为0.5
• BPP 多项式运行时间，错误概率小于0.5，双边错误
• RP 多项式运行时间，错误概率小于0.5，单边错误，可能弃真
• coRP 多项式运行时间，错误概率小于0.5，单边错误，可能取伪
• ZPP 期望多项式运行时间，错误概率伪0，或者允许 0,1,? 三种输出。
• MonteCarlo: BPP,RP,coRP，错误有界最坏多项式
• LasVegas: ZPP，零错误期望运行时间
• $\rm BPP \sube P/poly = PSIZE$ ，方法是 $2^n2^{-poly(n)}<1$，所以可以存在一个随机串对所有长度为n的输入给出正确答案，固化到电路中即可。
• KL定理说如果PH不塌则随机算法不能解决NP完全问题。
• 如何判断两张图非同构，随机选一张图，让对方输出同构的图，如果非同构概率为1，同构概率为1/2

交互式证明

• AM,MA,IP

主要是完全问题，NP完全，NL完全，PSPACE完全

子归约性，复杂度性的包含关系，谁包含谁，出判断题的话就是：对,错,不知道