\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)
一个语言是可判定的，当且仅当该语言和该语言的补集都是图灵可识别的。
二教316考试
复杂性类
递归定理：你可以递归
归约
泵引理，正则语言版：
- 存在常数 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)$
- $A=\set{w\mid \exist 字符串c，算法V接受 \left
$\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 A \le_m^p B\ via\ f$ 说明
$\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$ 的几个子句是什么。增加一些补充的凑数的变量。
- $\rm VERTEXCOVER={(G,k)|无向图G有k 个顶点的顶点覆盖}$
按照可近似性分类
- 完全多项式时间近似方案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)$。
- 猜测拒绝的串，用非确定性线性空间追踪NFA状态。（如果某个时刻所有标记都不落在接受状态上，则接受；否则拒绝。
已知 $\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$。
证明思路是：
由于最多只有 $f(n)$ 的空间，也就是 $f(n)$ 的格局大小，所以不同的数量是 $2^{O(f(n))}$ ，可以运行 $2^{O(f(n))}$ 步。这样就知道
- $\rm NSPACE(f(n)) \sube NTIME(2^{O(f(n))})$
利用 $\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 完全的$
- 证明思路是用递归算法，把画面分成两半。
- 证明是PSPACE的，通过递归代入。
- 证明别的被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)$ 是否可以作为一条边。
- 算出来有这么多个点之后，如果和之前的相等说明就这么多。
交错式
这门课好棒啊呜呜呜
- 交错式图灵机(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完全
子归约性，复杂度性的包含关系，谁包含谁，出判断题的话就是：对,错,不知道