浙江大学计算理论复习总结

浙江大学2012-2013冬学期计算理论重点复习一个学期的计算理论课程已经结束，给我的感觉吧，计算理论是一门计算机不得不学，学了短期又没用，但是可以培养一些逻辑思维的课程。其最关注的问题是什么是可计算性，什么问题可计算，问题之间的映射/归约，计算代价及难易。在分析问题和检验模型计算能力之前需要掌握的工具是形式语言、图灵机等。本文主要对计算理论中的重点进行了总结，总结了一些定理和理解上容易有障碍的知识点，但是里面还有一些点没有提到，比如NFA、DFA的相互转化，CFL和PDA的相互转化，需要书中的题目和证明辅助。TextbookSummary1.与自然数集合N等势的集合是可数无穷的，称有穷的or可数无穷的集合是可数的。非可数的集合称作不可数的。2.DFA(K,Σ,s,F,δ)；NFA（K,Σ，s，F，Δ）3.每台NFA都有一台等价的DFA（method:findclosure）4.有穷自动机接受的语言类=正则语言类（正则表达式描述的语言类）5.正则语言在各种运算下封闭6.语言是正则的，iff其等价语言中有有穷个等价类。7.DFA状态最小化-寻找等价类（初始等价类F&K-F）8.CFL（V，Σ，R，S）9.存在非正则的CFL10.能够生成=两棵语法分析树的字符串的文法叫做歧义的。11.PDAM=（K，Σ，Γ，Δ，s，F），Γ为栈符号12.PDA接受的语言正好是CFL13.正则语言（xynz）和CFL（uvnxynz）的泵定理14.L={anbn}∈CFL，L={anbncn}∉CFL但是是递归的，L={an,n为素数}不是CFL15.Chomsky范式（CNF）：若R⊆(V-Σ)×V2，则称G=（V，Σ，R，S）为Chomsky范式16.有穷自动机总是停机。17.CFG到CNF的转化：1)消除长rules2)消除空rules（A-e）3)消除短rules（A-aorA-B）18.对任意CFLG，都可以在多项式时间构造Chomsky范式G’,使得L(G’)=L(G)-(Σ∪{e})19.没有chomsky范式能够表示length2的字符串，所以包含2的字符串的语言不能转化到chomsky范式。20.确定型CFL（确定型PDA接受的语言类）在补下封闭。21.TM(K，Σ，δ，s，H)，注意字母表Σ不包含←和→22.若存在TM判定L，则称L是递归的。23.如果对于所有w属于Σ*，M(w)=f(w)，我们说M计算函数f，若存在TM计算f，则f称为递归的。24.半判定语言的TM都不是算法25.多带、多带头、双向无穷带or多维带的TM，其判定or半判定的任何语言及任何函数，都分别可用标准TM判定、半判定or计算。26.非确定型TM：一个格局可在一步里产生多个其他格局，NDTMisnomorepowerfulthanoriginalTM27.若非确定型TMM半判定或者判定语言L，或者计算函数f，则存在标准型TMM’半判定or判定L，or计算函数f。28.文法是CFG的推广，任何CFG都是文法。G=（V，Σ，R，S）29.语言被文法生成iff它是r.e.的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题：H={“M””w”:M在w上停机}﹁H={“M””w”：M是一台在”w”上不停机的TM}H1={“M”：M在“M”上停机}﹁H1={w：要么w不是一台TM的编码，要么w是M的编码，M是一台在”M”上不停机的TM}H：r.e.;H1：r.e.；﹁H,﹁H1：非r.e.；2-SAT∈P；SAT∈NP33.没有算法的问题称作不可判定的or不可解的，如TM的停机问题34.证明不可判定：从通用图灵机U通过递归函数归约到L，如果L是递归的则U是递归的。i.e.若L1非递归，并存在L1到L2的归约，则L2也非递归。递归函数是TuringComputable的。35.语言是图灵可枚举的，iff存在枚举它的图灵机。（M通过空格代开始，周期性的经过特殊状态q来枚举L，任意顺序且可重复）36.不可判定语言与递归语言互为补集，与r.e.语言有交集。37.语言是r.e.，iff它是图灵可枚举的；语言是递归的，iff它是以字典序Turing可枚举的。38.P在并交连接和补运算下封闭，NP在并、连接运算下封闭。若NP在补下封闭，则NP=P。39.H={“M””w”:M在最多2|w|步后停机}∉P40.所有正则语言和所有CFL都属于P41.NP：A.机器角度去定义：被多项式界限非确定型图灵机判定的所有语言的类。B.基于verifier的定义：NP问题上建立的非确定机包含两步：1)非确定地猜一个解2)用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题这两个定义是不矛盾的，因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的输入是否满足，就是基于verifier的定义。（可满足性）的算法称作verifier，一个问题称作NP问题当且仅当存在一个多项式时间的verifier。P和NP的区别：AproblemisinPifwecandecidetheminpolynomialtime.ItisinNPifwecandecidetheminpolynomialtime,ifwearegiventherightcertificate.42.若存在计算函数f的多项式界限的图灵机M，则f称为多项式时间可计算的。43.若τ1是L1-L2的多项式归约，τ2是L2-L3的多项式归约，则τ1·τ2是L1-L3的多项式归约。44.证明NP完全：法一、按定义：L⊆Σ*，若（a）L∈NP，且（b）对每个语言L’∈NP，存在从L’到L的多项式归约则L称为NP完全的。法二、归约，对于语言L，（a）若L∈NP（b）一个NP完全问题可以在多项式时间规约到L，i.e.SAT≤pL则L称为NP完全的。45.L是NP完全语言，则P=NP，iffL∈P46.SAT是NP-complete，3-SAT，最大可满足性也是NP完全的47.覆盖问题，Hamilton圈（有向无向），旅行商问题，背包问题都是NP-complete。48.a*b*c*-{anbncn,n≥0}iscontext-freebutnotregular49.L=L1L2，L是CFL，则L1一定是CFL（×）50.Regular-CFL不一定是CFL，如a*b*c*-anbn包含anbncn51.2-wayPDA(i.e.PDAwhoseinputheadscanmovebothleftandright)aremorepowerfulthan1-wayPDA52.GivenaPDAM1andanFAM2,theproblemL(M1)⊆L(M2)isdecidable53.DFA/NFA识别的是exactly正则语言。54.R.e.只在补和差下不封闭，CFL在交下也不封闭。55.非正则语言的*可能是正则语言。比如A:{w=wR},及所有回文，A*=Σ*，为正则语言56.典型非正则：w=wR57.正则语言的子集可能非正则，如anbncn,是a*b*c*的子集；又如Σ*是正则语言，H⊆Σ*。58.归约：X到Y的归约可以理解为X到Y问题的映射,reduction可以解释为atleastasdifficultas…比如X可以被Y的算法解决，则XisnomoredifficultthanY,X可以归约到Y，记X≤Y。e.g.x2可以归约到任意两数的乘积。∴若有A≤rB，A是不可判定问题-B不可判定A不递归-B不递归B可判定-A可判定B是递归的-A是递归的59.若X多项式时间归约到Y，Y多项式时间可解，则X多项式时间可解；若X多项式时间归约到Y，X多项式时间不可解，则Y多项式时间不可解60.X多项式时间归约到Y，Y多项式时间归约到Z，则X多项式时间归约到Z61.PRIME（COMPOSITE）多项式时间归约到Factor，但是Factor多项式时间不能归约到PRIME（COMPOSITE）。62.若A≤PB，B∈NP，则A∈NP。证明：A≤PB⇒存在确定图灵机X，可将A归约到B。B∈NP⇒存在一个非确定图灵机N可判定B。我们希望构造一个新的TM（X*N），是的X*N非确定多项式时间求解A，则A∈NP。RunningtimeofX*N≤1+p(n)A-B+q(p(n))(B多项式时间非确定判定)是多项式时间所以A∈NP63.若A≤PB，B∈P，则A∈P。64.若X是NPC的，则X在多项式时间内可解iffP=NP.65.SAT多项式时间归约到3-SAT(3-SAT是NPC的)66.证明语言L是R./R.e./NonR.e.a)Intuitively想想有没有半判定（判定）的TM，有则R.e.(R)。若非R,执行下一步。b)用能否由R.e.（NonR.e.）语言归约到该语言，能则R.e.而非R（NonR.e）.严格用归约函数定义f：A≤pB，r1∈A当且仅当f(r1)∈Be.g.1M,w∈H,iffM∈L证明R.e.e.g.2M,w∈非H，iffM∈L证明NonR.e.注意方向：是从A的实例经过递归函数推向B的实例。详细介绍：~nakhleh/COMP481/final_review_sp06_sol.pdf67.递归与μ递归等价68.PDA中，若每一个格局至多有一个格局接在它后面，则为确定型的。确定型CFL在补下封闭。69.M半判定L：w∈L，iffM在w上停机，注意半判定图灵机中不存在“拒绝”状态。只要不接受w，就不停机。70.Chomskyhierarchy71.俩证明：7.6证明P在并、交、Kleene*连接和补运算下封闭。(1)并：对任意L1,L2∈P，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1∪L2构造判定器M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”时间复杂度：设M1为O(na),M2为O(nb)。令c=max{a,b}。第一步用时O(na+nb)，因此总时间为O(na+nb)=O(nc),所以L1∪L2属于P类，即P在并的运算下封闭。(2)连接：对任意L1,L2属于P类，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1L2构造判定器M:M=“对于输入字符串w=w1,w2,…,wn，1)对k=0,1,2,…,n重复下列步骤。2)在w1w2…wk上运行M1，在wk+1wk+2…wn上运行M2。3)若都接受，则接受。否则继续。4)若对所有分法都不接受则拒绝。“时间复杂度：(n+1)×(O(na)+O(nb))=O(na+1)+O(nb+1)=O(nc+1)，所以L1L2属于P类，即P在连接的运算下封闭。(3)补：对任意L1属于P类，设有时间O(na)判定器M1判定它，对1L构造判定器M:M=“对于输入字符串w:(1)在w上运行M1。(2)若M1接受则拒绝，若M1拒绝则接受。”时间复杂度为：O(na)。所以1L属于P类，即P在补的运算下封闭。7.7证明NP在并和连接运算下封闭。(1)并：对任意L1,L2∈NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1∪L2的非确定图灵机M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。所以L1∪L2∈NP，即NP在并的运算下封闭。(2)连接：对任意L1,L2∈NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w:1)非确定地将分成两段x,y，使得w=xy。2)在x上运行M1，在y上运行M2。3)若都接受则接受，否则拒绝