资源描述：
《算法与计算复杂性课程(9)NP完全理论.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、NP完全理论的基本概念判定问题和语言判定问题定义与描述判定问题与语言的关系P类与NP类难解的问题与多项式可解的问题P类与NP类定义多项式变换与NP完全性多项式变换的定义及性质NP完全的定义Cook定理1判定问题和语言判定问题的定义陈述判定问题的标准格式引入判定问题的理由判定问题的形式描述——语言算法的形式描述——Turing机2判定问题的定义和描述定义一个判定问题π=(Dπ,Yπ),其中Dπ为实例集,Yπ⊆Dπ为肯定实例的集合.任给实例I∈Dπ,问I∈Yπ?陈述一个判定问题的标准格式对实例中参数的
2、一般描述和一个肯定--否定问题.子图同构问题实例:两个图G=(V,E),G=(V,E)111222问:G是否包含与G同构的子图?即是否存在子集12V’⊆V,E’⊆E使得
3、V’
4、=
5、V
6、,
7、E’
8、=
9、E
10、,且有双射f:1122V→V’满足以下条件?2{u,v}∈E⇔{f(u),f(v)}∈E’23引入判定问题的理由•判定问题的形式化描述简单.•许多优化问题的难度与判定问题的难度相关.判定问题∝优化问题将判定问题转换为优化问题.时间为O(g(n))调用解优化问题的算法求解优化问题.时间为O(f(n))
11、用优化问题的解得到判定问题的解.时间O(h(n))总时间：O(g(n)+f(n)+h(n))g(n)和h(n)为o(f(n))，判定问题时间为O(f(n))实例：巡回售货员问题是优化问题.如果在实例中加上参数B,问是否存在长度不超过B的旅行?得到对应的判定问题.4判定问题的形式描述语言的定义∑为有穷字符集∑*是∑上所用有穷字符串的集合∑*的任何子集为∑上的语言判定问题与语言的关系在合理的编码系统e下,判定问题的任意实例被编码成一个字符串xc1巡回售货员问题的实例1059相应的字符串是:c26c3∑
12、={c,[,],/,0,1,2,3,4,5,6,7,8,9,#}93c[1]c[2]c[3]c[4]//10/5/9//6/9//3#25C=255c4判定问题的形式描述（续）编码系统e将∑*中的字符串划分成三类:不是实例中的编码Dπ－Yπ中的实例的编码Yπ中的实例的编码Yπ中的实例的编码构成与判定问题π对应的语言L.具体定义如下:与判定问题π和编码系统e相关的语言L[π,e]设π为判定问题,e是关于π的编码系统,其字符表为∑,L[π,e]={x∈∑*:x是某个实例I∈Yπ在e下的编码}I∈Yπ⇔
13、x∈L[π,e]6算法的形式描述算法解判定问题π⇔用Turing机识别语言L[π,e]说明：对判定问题π,相关的L[π,e]与编码系统e有关.合理的编码系统:无冗余的符号和信息.数字用二进制(或其他进制，不允许用一进制）表示.可译码在不同的合理的编码系统下,实例的编码所对应的输入长度length:Dπ→Z+多项式相关.换句话说,e,e’为合理的编码系统,实例I在e和e’下的编码所对应的输入长度分别为length[I]和length’[I],则存在多项式P和P’使得length’[I]≤P(leng
14、th[I]),length[I]≤P’(length’[I])7P类与NP类难解的问题定义实例P类与NP类的定义非形式定义（问题类）形式定义（语言类）P类与NP类的关系P⊆NPP=NP?8难解的问题定义：不存在确定型多项式时间算法的问题难解的原因•问题太难,在多项式时间不可能找到解•解本身太庞大,表示解的符号串长度不是输入长度的多项式函数一般只考虑第一种难解的问题两类难解的问题不可判定问题——不存在算法可判定的难解问题——有算法，但不存在多项式时间的算法9实例---不可判定问题停机问题是不可判定的
15、定理1不存在根据任意Turing机T的定义,能够确定T在输入d上是否停机的算法.T证明思路：证明T在输入T上停机是不可判定的反证法：假设存在Turing机H，可以对任何Turing机T，判定T在T上是否停机.根据H，构造Turing机L,使得对于L产生如下悖论：L在L上停机⇒L在L上不停机L在L上不停机⇒L在L上停机10证明证假定H是可判定T在T上是否停机的Turing机.H有两个停机状态:Yes停机状态⇔T在T上停机No停机状态⇔T在T上不停机构造新的Turing机L.L比H多两个新的状态q’,
16、q’.12H进入Yes停机状态当且仅当L转移到q’.并且设定转1移函数,∀u∈∑有δ(q’,u)=(q’,u,R)，δ(q’,u)=(q’,u,L)1221H进入No停机状态,L也进入No停机状态.从而有T在T上停机⇒L在T上不停机T在T上不停机⇒L在T上停机令T=L,则导致L在L停机⇒L在L上不停机L在L不停机⇒L在L上停机产生矛盾.11实例---可判定的难解问题非确定型的难解问题(用非确定型的Turing机在多项式时间不可能解出)判定半扩展正则表达式是否表示它的字母表上的所有的
