这是Sipser的《计算理论导引》的简要笔记. 计算理论还是比较难的......

前面文法看得相对多一点,后面就疯狂跳了.

第0章

计算理论主要包括三个部分,自动机理论,可计算性理论和复杂性理论.

字母表(alphabet)是一个非空有限集,其中的成员称为字母表的符号.字母表上的字符串(string)是字母表中元素的有限序列,元素的个数称为字符串的长度(记为$|w|$),长度为零的字符串称为空串(记为$\epsilon$). 字符串有子串,前缀,拼接的概念. 字符串的集合被称为语言(language).

第1章正则语言

有限自动机

(确定性)有限自动机(DFA)是一个五元组$M=(Q,\Sigma,\delta,q_0,F)$,其中$Q$为状态的有限集,$\Sigma$为字母表,$δ:Q\times\Sigma\to Q$为转移函数,$q_0\in Q$为初始状态,$F\subseteq Q$为接受状态集合.DFA可以用状态图表示.

设$w=w_1w_2\cdots w_n$是一个字符串,如果存在一系列状态$r_0,r_1,\cdots,r_n$使得$r_0=q_0$,$\delta(r_i,w_{i+1})=r_{i+1}$,$r_n\in F$,则称$w$被DFA$M$所接受.DFA$M$所接受的全体字符串$L(M)=\\{w\mid M接受w\\}$称为$M$所接受的语言.特别的,被某个DFA接受的语言称为正规语言(regular language).

对语言我们可以定义正则运算:并运算$A\cup B$,连接运算$A\circ B$,星运算(闭包运算)$A^*$.通过构造DFA乘积的方式我们可以证明正则语言的并还是正则语言.

非确定性

非确定性有限自动机(NFA)是一个五元组$N=(Q,\Sigma,\delta,q_0,F)$,其中$Q$为状态的有限集,$\Sigma$为字母表,$δ:Q\times(\Sigma\cup\epsilon)\to\mathcal{P}(Q)$为转移函数,$q_0\in Q$为初始状态,$F\subseteq Q$为接受状态集合. NFA也可以用状态图表示;它与DFA的主要区别在于可以同时处在多个状态,并且可以进行空串$\epsilon$的转移.

设$w=w_1w_2\cdots w_n$是一个字符串,如果在其中插入一些$\epsilon$得到$w=v_1v_2\cdots v_m$,并且存在一系列状态$r_0,r_1,\cdots,r_m$使得$r_0=q_0$,$r_{i+1}\in\delta(r_i,v_{i+1})$,$r_m\in F$,则称$w$被NFA$N$所接受.NFA$N$所接受的全体字符串$L(M)=\\{w\mid N接受w\\}$称为$N$所接受的语言.

NFA与DFA是相互等价的.要证明这一点,只需要证明任意NFA都有等价的DFA(即能够接受相同的语言).首先对任意的NFA,改变其转移函数为$\delta'(r,a)=\\{(r',a)\mid 从\delta(r,a)出发经过若干次\epsilon转移可以到达r'\\}$,这样就消去了NFA中所有的$\epsilon$转移. 其次对没有$\epsilon$转移的NFA,以其状态集$Q$的子集$\mathcal{P}(Q)$为新的状态集,子集$R\subseteq\mathcal{P}(Q)$的状态转移为$\delta'' (R,a)=\cup_{r\in R}{\delta'(r,a)}$,从而构造出一个DFA.可以看出NFA与这个DFA是等价的.

通过"并联"和"串联"两个NFA,可以证明正则语言的并和连接依然是正则语言;通过连接接受状态到初始状态构造NFA,可以证明正则语言的星运算依然是正则语言.

正则表达式

从字母,$\epsilon$,$\emptyset$出发经过有限次正则运算得到的表达式称为正则表达式.

正则表达式与DFA等价(也与正则语言等价).这是因为,一方面可以构造接受字母,$\epsilon$,$\emptyset$的NFA,再由正则运算的封闭性可知,任意正则表达式可由NFA接受,亦可由DFA接受;另一方面,设有一个DFA,把转移的字母变为正则表达式得到一个推广的自动机GNFA,对GNFA的状态个数归纳可以构造出DFA接受的正则表达式.(这部分过程比较复杂;此外另一个方向也有一种直接的证明,通过归纳构造从状态i到j且经过的状态编号不超过k的所有字符串对应的正则表达式,可见Hopcroft的书)

非正则语言

对于正则语言,有如下的泵引理:对任一正则语言$A$,存在一个整数$p$使得对任何$A$中的字符串$\mid s\mid\ge p$,$s$可以被分为$s=xyz$使得:1.对任何非负整数$i$,$xy^iz$属于$A$; 2.$\mid y\mid >0$; 3.$\mid xy\mid\le p$.

这个引理成立的原因在于,若$A$对应的DFA有$p$个状态,那么对于长度大于等于$p$的字符串$s$,它必然经过$p+1$个状态,由抽屉原理必然经过两个相同的状态;根据这两个相同的状态将$s$分为三个部分,几个性质即可得证.

泵引理主要用于证明一些语言不是正则语言.

第2章上下文无关语言

上下文无关文法

上下文无关文法(CFG)是一个四元组$G=(V,\Sigma,R,S)$,其中$V$为变量集,$\Sigma$为(终结)符号集,$R$为规则集合(每条规则包括一个变量和一个由变量和符号组成的字符串,即$R\subseteq V\times (V\cup\Sigma)^*$,一般写成$A\to w$的形式),$S\in V$为初始变量. 如果有多个规则从同一个变量$A$导出多个字符串$w_1,\cdots,w_n$,那么通常简写为$A\to w_1|\cdots|w_n$.

对于两个由变量和符号组成的字符串$u,v$,如果$A\to w$是一条规则,将$u$中的某一个$A$替换为$w$即得到字符串$v$,那么称$u$派生$v$,记作$u\implies v$. 由初始变量派生的仅含符号的字符串全体称为CFG$G$派生的语言,由某个CFG派生的语言称为上下文无关语言(CFL).

任何正则语言都是CFL.这是因为正则语言对应DFA,将DFA的每个状态对应一个变量,根据转移函数和起始/接受状态就能得到一个CFG.

如果在派生某个字符串$w$的过程中,总是替换最左边的变量,则称这样的派生是最左派生;具有两个不同的最左派生的字符串被称作被有歧义地派生(derived ambiguously).存在某个有歧义地派生的字符串的CFG被称为有歧义的文法.仅能由有歧义的CFG派生的CFL被称为内在歧义的语言.这样的语言是存在的.

如果CFG$G$的每条规则形如$A\to BC$($B$,$C$均为非初始的变量)或者$A\to a$(a为某个符号),那么这样的CFG被称为Chomsky标准文法.任何一个CFL均可由某个Chomsky标准文法派生.这是因为,首先添加一个新的初始变量使得后续不会出现初始变量;接着通过添加规则的方式可以消去所有派生出$\epsilon$的规则;然后通过替换的方式可以消去所有只派生一个变量的规则;最后对于剩下的规则,通过两两合并的方式可以转换为标准文法的规则(变量对应第一种规则,符号先变成变量再对应第二种规则).

下推自动机

下推自动机(PDA)是一个六元组$M=(Q,\Sigma,\Gamma,\delta,q_0,F)$,其中$Q$为状态集合,$\Sigma$为输入符号集合,$\Gamma$为栈符号集合,$\delta:Q\times(\Sigma\cup\epsilon)\times(\Gamma\cup\epsilon)\to\mathcal{P}(Q\times(\Gamma\cup\epsilon))$为转移函数,$q_0\in Q$为初始状态,$F\subseteq Q$为接受状态集合.

设$w=w_1w_2\cdots w_n,w_i\in(\Sigma\cup\epsilon)$是输入序列,如果存在一系列状态$r_0,r_1,\cdots,r_n\in Q$和栈序列$s_0,s_1,...,s_n\in\Gamma^*$,使得$r_0=q_0,s_0=\epsilon$,$(r_{i+1},b)\in\delta(r_i,w_{i+1},a)$其中$s_i=at,s_{i+1}=bt$,并且$r_n\in F$,则称$w$被PDA$M$接受.$M$所接受的所有字符串构成$M$所接受的语言.

可以看到PDA和NFA的不同主要在于PDA具有一个栈,以及出栈入栈的能力. 此外,PDA本身的机制并不能给栈初始化,转移时多个字符入栈,判断栈空或是判断输入结束;但是通过适当添加符号和状态,即可实现这些功能.

PDA与CFG等价.这是因为,一方面对于任一CFG派生出的CFL,我们构造状态使得:如果输入和栈顶都为某个符号,则该符号可以出栈;如果输入为$\epsilon$而栈顶为某个变量,则可以按照CFG的规则将该变量出栈,由规则派生的字符串入栈.当栈空时即接受输入.这样构造出的PDA可以接受该语言. 另一方面,对于任意PDA,不妨设它只有一个接受状态,接受前栈为空,且每次转移要么只出栈要么只入栈.以输入符号为文法的符号,且对于每对状态$(p,q)$构造变量$A_{pq}$.建立三种规则:如果从状态$p$输入$a$并入栈$u$可以转移至$r$,并且从状态$s$输入$b$并出栈$u$可以转移至$q$,那么建立规则$A_{pq}\to aA_{rs}b$;对于任意状态$p,q,r$,建立规则$A_{pq}\to A_{pr}A_{rq}$;最后建立规则$A_{pp}\to\epsilon$.可以证明,这样构造的$A_{pq}$生成的字符串对应所有从状态$p$和空栈出发能够转移至状态$q$和空栈的输入符号串.这样,以初始状态和接受状态构造的变量$A_{q_0q}$为初始变量即得等价的CFG.

非上下文无关语言

CFL也有泵引理,其内容为:设$A$为CFL,则存在一个正整数$p$使得,只要$A$中的字符串$s$满足$\mid s\mid\ge p$,那么可以将其分为五部分$s=uvxyz$,使得:1.对任意非负整数$i$,$uv^ixy^iz$属于$A$;2.$\mid vy\mid >0$;3.$\mid vxy\mid\le p$.

要证明它,只需要注意$A$的CFG中变量的个数有限.当$s$的长度充分长时,考虑从起始变量出发得到$s$的解析树,这个树足够深,于是根据抽屉原理,从根到某个叶子上必然经过两个相同的变量.根据这两个重复变量生成的子树,可以将$s$分成五个部分,再注意到用相同变量生成的子树替换后仍为合法的字符串,三个性质即可得证.

这个引理也可以被用来证明一些语言不是CFL.

确定性上下文无关语言

(这一节的内容比较难,所以我只是粗略的看了一部分)

与(非确定性)下推自动机相比,确定性下推自动机(DPDA)允许了$\epsilon$转移的存在,但对于每个状态,输入和栈,要求至多转移转移到一个状态(也允许不转移);并且输入为$a$或$\epsilon$,栈顶为$x$或$\epsilon$时,四种情况必须有一种可以转移.DPDA接受的语言称为确定性上下文无关语言(DCFL). DCFL对补预算封闭,由此可以得到是CFL但不是DCFL的语言存在.

对应也有确定性上下文无关文法(DCFG),主要是在CFG的基础上要求每个字符串倒推回起始变量的过程具有唯一性.具体地说,如果字符串$u$中的某一字串$h$可以按照规则$T\to h$倒推,那么称$h$是$u$的一个句柄(handle);如果$h$是$v=xhy$的句柄并且对任何$\hat{y}$,$h$都是$xh\hat{y}$中的唯一句柄,则称$h$是$v$的强迫句柄(forced handle);如果每个合法字符串都有一个强迫句柄则称该文法为DCFG.判断一个CFG是否为DCFG有一个测试方法叫做DK测试.事实上,DCFG和DPDA是等价的.

第3章 Church-Turing论题

图灵机

图灵机(TM)是一个七元组$M=(Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject})$,其中$Q$是状态集合,$\Sigma$是输入符号集合(不包含空符号),$\Gamma$为纸带符号集合(包含空符号和$\Sigma$),$:QQ\{ L,R \} $为转移函数,$q_0Q$为初始状态,$q_{accept}Q$为接受状态,$q_{reject}Q$为拒绝状态.

图灵机在工作时包括三个要素:状态,纸带内容,纸带头位置,它们合起来叫做图灵机的一个配置(configuration),可以用$u\,q\,v$表示纸带内容为$uv$,状态为$q$且纸带头指向$v$的第一个字符.配置的转移方式是:如果$\delta(q_i,b)=(q_j,c,L)$,那么$ua\,q_i\,bv$可以转移到$u\,q_j\,abv$;如果$\delta(q_i,b)=(q_j,c,R)$,那么$ua\,q_i\,bv$可以转移到$uab\,q_i\,v$.一个例外是在纸带最左端向左移动,纸带头位置不变.

当输入字符串$w$时,图灵机以$q_0\,w$为初始配置.如果经过有限次转移后图灵机进入$q_{accept}$,则称该图灵机接受(识别)该字符串;该图灵机接受的全体字符串称为该图灵机接受的语言;被某个图灵机接受的语言称为图灵可识别语言(Turing-recognizable,或称递归可枚举语言).如果该图灵机对于任意输入,经过有限次转移后总是进入$q_{accept}$或是$q_{reject}$,则称该图灵机是判定机(decider);判定机识别的语言称为被该图灵机所判定的语言;被某个图灵机判定的语言称为图灵可判定语言(Turing-decidable,或称递归语言).

图灵机的变种

给图灵机添加多个纸带即得到多纸带图灵机,它能够在多个纸带上同时修改,并且具有多个纸带头.多纸带图灵机的运算能力与图灵机等价,因为我们可以通过给不同纸带的字符串之间插入分隔符#的方式用单纸带模拟多纸带,并通过在符号上添加点(可以理解为替换成对应符号)表示多个纸带头的位置,当修改到多纸带上的空字符时将对应单纸带上的内容平移.

允许图灵机转移至多个状态即得到非确定性图灵机.非确定性图灵机的运算能力与图灵机等价,因为我们可以将非确定性图灵机的运行看作一棵树,对这棵树做BFS即可模拟非确定性图灵机.

算法的定义

算法并没有一个严格的定义.Church-Turing论题认为,直观上的算法和图灵机所实现的算法是等价的.

第4章可判定性

可判定语言

语言$A_{DFA}=\\{(B,w)\mid B是某个接受字符串w的DFA\\}$是可判定的,因为我们可以用图灵机模拟DFA的运行.语言$A_{NFA}=\\{(B,w)\mid B是某个接受字符串w的NFA\\}$和$A_{REX}=\\{(R,w)\mid R是某个生成字符串w的正则表达式\\}$也是可判定的,因为我们可以将NFA和正则表达式转化为DFA.

语言$E_{DFA}=\\{A\mid A是一个DFA,且L(A)=\emptyset \\}$是可判定的,因为我们可以用图灵机对DFA遍历(搜索)其所有可能到达的状态,接受状态是否在其中就决定了这个DFA的语言是否为空.语言$EQ_{DFA}=\\{(A,B)\mid A,B是DFA,且L(A)=L(B)\\}$是可判定的,因为我们可以构造$L(A),L(B)$的对称差,因为正则语言对补交并封闭所以对称差是某个DFA的语言$L(C)$,因而可用$E_{DFA}$来判定相等.

语言$A_{CFG}=\\{(G,w)\mid G是某个派生字符串w的CFG\\}$是可判定的,因为我们可以将$G$转换为Chomsky标准文法,而它派生一个长度为n的字符串恰好要替换2n-1次,所以可以通过搜索判定$A_{CFG}$.语言$E_{CFG}=\\{G\mid G是某个CFG且L(G)=\emptyset\\}$是可判定的,因为我们可以从终结字符出发搜索确定每个变量是否能够派生出仅终结字符的字符串,进而判定$G$是否能派生出仅终结字符的字符串.

此外,任何CFL都是可判定的.这是因为我们可以直接利用$A_{CFG}$来判定某个字符串是否合法.

不可判定性

图灵不可识别语言必定存在,因为图灵机全体构成可数集而语言全体构成不可数集.

语言$A_{TM}=\\{(M,w)\mid M是接受字符串w的图灵机\\}$是图灵不可判定的.这是因为如果它可判定,设判定它的图灵机为$H$,那么可以构造图灵机$D$,输入一个图灵机$M$的编码,如果$M$接受$M$的编码那么$D$拒绝$M$的编码,反之接受.不论$D$接受还是拒绝$D$自身的编码,都会产生矛盾.

一个语言是图灵可判定的当且仅当它和它的补都是图灵可识别的.这是因为一方面如果它是图灵可判定的那它和它的补显然是图灵可识别的;反过来如果它和它的补都是图灵可识别的,那么我们可以构造一个图灵机来并行地判定它和它的补是否可识别,当其中一个停机时即判定成功.因为$A_{TM}$是图灵可识别的所以它的补是图灵不可识别语言.

第5章可归约性

可归约性可以用来证明不可判定性.如果某个问题A与问题B之间具有这样的性质:若找到了B的解决方法,那么A也能解决,那么(不严格地)就称A可以归约到B.可见如果A是不可判定的,那么B也是不可判定的.

语言中的不可判定问题

几个不可判定问题

停机问题$HALT_{TM}=\\{(M,w)\mid M在输入w下停机\\}$不可判定.这是因为,如果它可判定,我们可以构造一个图灵机用于判定$A_{TM}$:先判定是否停机,如果停机再对这个图灵机模拟.这说明$A_{TM}$可归约到$HALT_{TM}$,因此$HALT_{TM}$不可判定.

语言$E_{TM}=\\{M\mid M是一个图灵机且L(M)=\emptyset\\}$不可判定.这是因为,如果它可判定,对于任一图灵机$M$和输入$w$,我们构造图灵机$M_1$使得:若输入为$w$则由$M$处理,否则拒绝,于是判定$L(M_1)$是否为空就能判定$M$是否接受$w$.这说明$A_{TM}$可归约到$E_{TM}$,因此$E_{TM}$不可判定.

语言$REGULAR_{TM}=\\{M\mid M是一个图灵机且L(M)是正则语言\\}$不可判定.这是因为,如果它可判定,对于任一图灵机$M$和输入$w$,我们选取一个非正则语言,并构造图灵机$M_2$使得:若输入为该非正则语言则接受;否则让$M$处理$w$,若$M$接受$w$则$M_2$接受输入,于是判定$L(M_2)$是否正则就能判定$M$是否接受$w$.这说明$A_{TM}$可归约到$REGULAR_{TM}$,因此$REGULAR_{TM}$不可判定.

语言$EQ_{TM}=\\{(M_1,M_2)\mid L(M_1)=L(M_2)\\}$不可判定.这是因为,如果它可判定,对于任一图灵机$M$,我们判定它与拒绝所有输入的图灵机是否等价,那么就能判定$L(M)$是否为空.这说明$EQ_{TM}$可归约到$E_{TM}$,因此$E_{TM}$不可判定.

计算历史方法

计算历史就是图灵机在状态转移时构成的配置的序列.线性有界自动机(LBA)是要求纸带头不能超出输入部分的范围的图灵机.

语言$A_{LBA}=\\{(M,w)\mid M是接受输入w的LBA\\}$是可判定的.这是因为字母个数有限,因而LBA的可能配置个数是有限的,图灵机只需要模拟有限步即可做出判定.

语言$E_{LBA}=\\{M\mid M是一个LBA且L(M)=\emptyset\\}$不可判定.这是因为,如果它可判定,对于任一图灵机$M$和输入$w$,构造一个LBA$B$,它接受输入$x$当且仅当$x$是$M$接受$w$的一个计算历史.由于只需要检查起始和结束的配置以及相邻的配置是否符合要求,所以纸带头不需要超出输入部分.判断$B$是否为空即可判定$M$是否接受$w$.这说明$A_{TM}$可归约到$E_{LBA}$,因此$E_{LBA}$不可判定.

语言$ALL_{CFG}=\\{G\mid G是一个CFG且L(G)为全集\\}$不可判定.这是因为,如果它可判定,对于任一图灵机$M$和输入$w$,构造一个PDA$D$,它输入$M$的一个计算历史,如果三种情况之一发生就拒绝输入(要用非确定性并行地检测):1.第一个配置不是输入$w$的配置;2.最后一个配置不是处于接收状态;3.其中某个转移不是合法的转移.此外为了便于检查第三种情况,需要调整输入的顺序使得相邻的两个配置的方向恰好相反.

一个简单的不可判定问题

波斯特对应问题(PCP)是指给定一组两两配对的字符串,判定能否(可重复地)选出一些配对排列起来,使得被配对的双方分别拼成两个相同的字符串.PCP是不可判定的.证明的细节比较繁琐,大概思路是先转化为对第一个配对有要求的MPCP,假设MPCP可判定,对于任一图灵机$M$和输入$w$,如果某个配置可以转移到另一个配置就将其配对起来,由MPCP取出这样的配对序列,从而得到一个$M$接受$w$的状态序列,于是$A_{TM}$可归约到PCP.

映射不可规约性

如果存在一个图灵机$M$,如果输入$w$,那么$M$以纸带内容$f(w)$停机,则称$f$是可计算函数. 如果存在可计算函数$f$,使得对任意$w$,$w\in A$当且仅当$f(w)\in B$,则称语言$A$通过映射可归约到$B$,记作$A\le_mB$,$f$称作$A$到$B$的规约.

可归约性有这样的性质:如果$A\le_mB$,$B$可判定,则$A$可判定;如果$A\le_mB$,$A$不可判定,则$B$不可判定.此外,如果$A\le_mB$,$B$图灵可识别,则$A$图灵可识别.由此可以证明$EQ_{TM}$和它的补都是图灵不可识别的.

第6章可计算性高级专题

递归定理

递归定理说的是，如果$T$是一个二元计算函数$t$的图灵机,那么存在一个一元计算函数$r$的图灵机$R$,使得对任意的字符串$w$都有$r(w)=t(R,w)$.它体现了机器具有自指的能力. 为了证明这个定理,需要构造两个图灵机$A$和$B$:$B$输入一个字符串,构造一个可以输出该字符串的图灵机,将其编码并和输入的字符串连接起来输出.$A$无输入而输出$BT$的编码.最后将$ABT$连接起来作为$R$,此时的$R$接受字符串$w$,$w$和$B$的输出$ABT=R$作为$T$的输入,$T$的输出又作为$R$的输出,这就得到了$r(w)=t(R,w)$.

递归定理使得我们在构造图灵机时可以直接利用它自身的编码.作为其应用,语言$MIN_{TM}=\\{M\mid M是图灵机,且不存在和M等价的比M描述更短的图灵机\\}$不可判定;任何可计算一元函数$t$都有不动点,即存在图灵机$R$使得$t(R)=R$.

逻辑理论的可归约性

若只使用加法,则自然数上所有真命题(这里要求是前束的闭式)的集合$Th(\mathbb{N},+)$可判定.而若使用加法和乘法,则$Th(\mathbb{N},+,\times)$不可判定.进一步地我们还能证明Godel不完备性定理.

(这节的证明没怎么看懂,所以顺带后面两节我也跳了)

图灵可归约性

信息的定义

第7章时间复杂度

测量复杂度

设$M$为图灵机,则$M$的时间复杂度是一个函数$f:\mathbb{N}\to\mathbb{N}$,使得当输入的长度为$n$时,$M$的运行步数最多为$f(n)$.对于时间复杂度,我们可以使用微积分里的大O/小o记号.对于非确定性图灵机,其时间复杂度是每个分支中最多的运行步数.

设$t(n)\ge n$.任何时间复杂度为$t(n)$的多纸带图灵机等价于时间复杂度为$O(t^2(n))$的单纸带图灵机;这是因为多纸带图灵机每执行一步,对应单纸带图灵机至多执行$O(t(n))$步.并且,任何时间复杂度为$t(n)$的非确定性图灵机等价于时间复杂度为$2^{O(t^2(n))}$的确定性图灵机;这是因为非确定性图灵机的分支个数至多为指数增长.

P类问题

P是所有能被(单纸带确定性)图灵机以多项式时间($O(n^k)$)判定的语言组成的类.P类问题在多项式等价(即一个图灵机以多项式的时间增长为代价模拟另一个图灵机)下等价;P类问题往往代表现实中计算机可解的问题.

P类问题的例子包括:判定两点之间是否联通的问题$PATH$,判定两个数是否互素的问题$RELPRIME$,任一上下文无关语言(将其CFG转换为Chomsky标准文法,然后用动态规划判定).

NP类问题

NP是所有可被多项式时间下验证(即存在一个图灵机$V$,使得该语言$A=\\{w\mid 存在某个字符串c,使得V接受(w,c)\\}$,且图灵机$V$相对于$w$的时间复杂度为多项式时间)的语言组成的类;同时也是所有可被某个非确定性图灵机在多项式时间下判定的语言组成的类.

NP类问题的例子包括:判定图中是否存在k-完全子图的问题$CLIQUE$,判定给定若干数中是否可以选出一些数使得其和等于给定的t的问题$SUBSET-SUM$.

NP完全

多项式时间规约,NP完全

如果存在一个图灵机$M$,使得它输入$w$时在多项式时间内停机且输出$f(w)$,那么称$f$是多项式时间可计算函数. 如果存在一个多项式时间可计算函数$f$使得对任意$w$,$w\in A$当且仅当$f(w)\in B$,则称语言$A$多项式时间下可规约到语言$B$,记作$A\le_PB$.

如果$A\le_PB$,并且$B\in P$,那么$A\in P$.

一个语言$B$,如果$B\in NP$,并且对任意的$A\in NP$,都有$A\le_PB$,那么就称$B$是NP完全(NPC)的.NP语言具有这样的性质:如果$B$是NP完全的,且$B\le_PC$,那么$C$也是NP完全的.

去掉$B\in NP$的条件,就称$B$是NP难的.

Cook-Levin定理

判定某个命题逻辑的公式能否在某个个体变元指派下为真(即判定该公式是否可满足)的问题叫做可满足性问题,记作$SAT$.Cook-Levin定理说的是$SAT\in NPC$. 证明的思路在于,首先$SAT\in NP$显然;其次若$A\in NP$,把$A$输入$w$后从起始到接受的那个分支的配置排成一列得到一个表格,然后根据表格上某个位置是否为某个字符得出若干个体变元,根据转移合法性的要求列出一个可满足的公式.这个公式生成的时间是多项式的,所以$A\le_PSAT$.

此外,如果要判定的公式是一个每一析取项仅由三个变元组成的合取范式,那么就得到$3SAT$问题.$3SAT\in NPC$,因为对于任意$SAT$中的公式,我们总可以先转化为合取范式,并且对于多于三个变元的析取项,我们总是可以利用$a_1\vee a_2\vee a_3\vee a_4=(a_1\vee a_2\vee z)\wedge(a_3\vee a_4\vee\bar{z})$来转化成三个变元的.因此$SAT\le_P3SAT$.

其他的NP完全问题

$CLIQUE\in NPC$.这是因为给定一个$3SAT$中的公式,我们以每个析取项的三个变量为顶点,将不同项之间没有互斥关系(即$x$和$\bar{x}$不能连接)的顶点连接起来,则判定此图有没有k-完全子图(这里k是析取项的个数)即可判定此公式是否可满足.

判定图中是否存在覆盖所有边的顶点集的问题叫做顶覆盖问题,记作$VERTEX-COVER$.$VERTEX-COVER\in NPC$.这是因为给定一个$3SAT$中的公式,将公式中的每个析取项作为三个相邻顶点,再为每个变量$x$建立两个相邻顶点$x$,$\bar{x}$,最后将这些顶点与相同的析取项中的顶点连接.判定此图有没有顶覆盖即可判定此公式是否可满足.

判定有向图中两顶之间是否存在Hamilton圈的问题记作$HAMPATH$.$HAMPATH\in NPC$.同样的,无向图版本的$UHAMPATH\in NPC$.此外$SUBSET-SUM\in NPC$.(这些的证明我跳过了)

第8章空间复杂度

设$M$为图灵机,则$M$的时间复杂度是一个函数$f:\mathbb{N}\to\mathbb{N}$,使得当输入的长度为$n$时,$M$使用的纸带单元个数最多为$f(n)$.对于非确定性图灵机,用某个分支上最多使用个数定义.

Savitch定理

Savitch定理说的是,设$f(n)\ge n$,如果一个非确定性图灵机的空间复杂度为$f(n)$,那么它等价于某个空间复杂度至多为$O(f^2(n))$的确定性图灵机.这是因为从一个非确定性图灵机出发,我们可以采取二分递归搜索的方式确定从起始到结束是否能在至多$2^{df(n)}$步内转移;因为搜索是递归的,所以可以重复利用同层的空间.

PSPACE类

PSPACE类由所有具有多项式空间复杂度的语言组成.NPSPACE对应非确定性的情形;根据Savitch定理,$PSPACE=NPSPACE$.

PSPACE完备

如果一个语言$B$满足:1.$B\in PSPACE$;2.对任何语言$A\in PSPACE$,$A$多项式时间可归约到$B$.则称$B$是PSPACE完备的.

PSPACE完备的例子包括:判断一个前束闭式是否为真的问题TQBF,判断在给前束闭式中的变量赋值的游戏中是否存在必胜策略的问题FORMULA-GAME,推广的地理游戏(两个人轮流沿着图走,第一个走到重复顶点的人输)是否存在必胜策略的问题GG,

L和NL类

NL完备

NL=coNL

第9章难解性

层次定理

设$f(n)$至少为$O(n\log n)$.如果存在一个图灵机,输入$n$个1能够输出$f(n)$的二进制,且空间复杂度为$O(f(n))$,则称$f(n)$空间可构造.将空间换成时间就得到时间可构造.

空间层次定理说的是对任何空间可构造的$f$,存在某个语言$A$,它能在$O(f(n))$的空间复杂度下被判定,却不能在$o(f(n))$的空间复杂度下被判定.大致思路是构造一个图灵机$D$,它接受一个图灵机的编码,并限制在$O(f(n))$的空间复杂度下模拟它,$D$所识别的语言即为所求;但实际上还需要做一些技术上的改正.

时间层次定理说的是对任何时间可构造的$t$,存在某个语言$A$,它能在$O(t(n))$的时间复杂度下被判定,却不能在$o(\frac{t(n)}{\log t(n)})$的时间复杂度下被判定.

两个层次定理表明,随着时间/空间复杂度的增长,所能识别的语言是会不断扩大的.

作为层次定理的应用,可以证明$EQ_{REX\uparrow}=\\{(Q,R)\mid Q,R是等价的扩展正则表达式\\}$(这里扩展正则表达式是指加入了指数运算的正则表达式)是EXPSPACE完备的,因而在时间和空间上都不可能以多项式时间判定.

相对化

一个谕示是一个能够直接判定某个字符串是否属于某个语言$A$的黑箱;带有谕示的黑箱的图灵机叫做谕示图灵机,记作$M^A$.

我们可以证明存在一个谕示$A$使得$P^A\neq NP^A$,又存在一个谕示$B$使得$P^B=NP^B$.

电路复杂性

第10章计算复杂度理论高级专题

近似算法

对于有些问题,求出最优解的算法是NP难的,此时也可以转而寻求不是最优的近似算法.如果某个算法的结果至少是最优算法的k倍(越低越优)或k分之一(越高越优),那么称该算法是k-最优的.

例如,对于求最小顶覆盖的问题MIN-VERTEX-COVER,如果随意找一条未被覆盖的边并标记它的某个顶点,不断进行下去,就得到一个多项式时间的2-最优算法.又例如求最大割的问题MAX-CUT,如果不断找出移动后能使割的容量增大的顶点就调整该顶点,直到无法调整(贪心),就得到一个多项式时间的2-最优算法.

概率算法

概率图灵机$M$是某些步有两个合法的随机转移方向,并且有$k$个随机转移的分支的概率为$2^{-k}$.此时$M$接受输入$w$的概率为所有接受$w$的分支的概率之和,拒绝$w$的概率为$1-Pr(M接受w)$.称$M$以错误概率$\epsilon$判定$A$,如果对任何$w\in A$,有$Pr(M接受w)\ge 1-\epsilon$,且对任何$w\notin A$,有$Pr(M拒绝w)\ge 1-\epsilon$.

BPP是所有能被概率图灵机以多项式时间和$\frac{1}{3}$的错误概率判定的语言.我们有放大引理:设$0\le\epsilon<\frac{1}{2}$,$p(n)$是多项式,则任一多项式时间的错误概率为$\epsilon$的概率图灵机等价于某个多项式时间的错误概率为$2^{-p(n)}$的概率图灵机.

判定一个数是否为素数,我们有Fermat检验法:随机挑选若干正整数$a_1,\cdots,a_k$,判断是否$a_i^{p-1}\equiv 1(\mod p)$.在此基础上进行二次探测,就得到Miller-Rabin素数判定算法;它检验一个奇合数时,错误的概率小于等于$2^{-k}$,进而属于BPP.

一个分支程序是一个有向无环图,其顶点除了两个输出顶点标号为0和1,其他用变量标号,并且总是有0和1两条出去的边.一个只读一次的分支程序是指从起点到输出顶点的所有可能路径上,标号不会重复的分支程序.判定两个只读一次的分支程序是否等价的问题$EQ_{ROBP}\in BPP$.

第0章

第1章 正则语言