第四讲完全性理论

第四讲完全性理论第1页，共47页，2023年，2月20日，星期三内容计算的形式描述－－计算模型可计算性理论P类与NP类问题NP完全性理论NP完全性的典型例子第2页，共47页，2023年，2月20日，星期三1理论计算模型－图灵机

A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。

图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。为算法和可计算性研究提供了形式化描述工具。第3页，共47页，2023年，2月20日，星期三FinitecontrolX1BB...X2XnXi带（tape）单元格（cell）带符（tapesymbol）读写头在每一时刻扫描带上的一个单元带有一个最左单元，向右则是无限的。带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n>＝0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。图灵机的基本模型第4页，共47页，2023年，2月20日，星期三图灵机（TuringMachine)带子可读可写无限长的带子读写头可左移右移有限状态控制器1111110000000BBB1…………第5页，共47页，2023年，2月20日，星期三 在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.将带头向左或者右移一个单元。。图灵机的工作机制第6页，共47页，2023年，2月20日，星期三图灵机的形式化描述有限状态集

有限输入符号集

有限带符号集

转移函数

开始状态

特殊带符:空白符

终态集合q0Q

T

B–T

FQ转移函数:QQ{L,R}形式定义一个图灵机TM(Turingmachine)是一个七元组

M=(Q,T,,,q0,B

,F).

第7页，共47页，2023年，2月20日，星期三其他图灵机模型“实际的”的图灵机模型单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价第8页，共47页，2023年，2月20日，星期三2P类与NP类问题算法的时间复杂度（分成二类）多项式时间指数时间可计算与不可计算第9页，共47页，2023年，2月20日，星期三

102030405060.00001.00002.00003.00004.00005.00006secondsecondsecondsecondsecondsecond.0001.0004.0009.0016.0025.0036secondsecondsecondsecondsecondsecond.001.008.027.064.125.216secondsecondsecondsecondsecondsecond.5.213.0secondsecondsecondminutesminutesminutes.0011.017.912.735.7366secondsecondminutesdaysyearscenturies.059586.538552*1081.3*1013secondminutesyearscenturiescenturiescenturiesnn2n3n52n3nSizenTimecomplexityfunction多项式与指数函数时间比较第10页，共47页，2023年，2月20日，星期三nn2n3n52n3nN1N2N3N4N5N6100N110N24.64N32.5N4N5+6.641000N131.6N210N33.98N4N6+4.19N5+9.97N6+6.29TimecomplexityfunctionWithpresentcomputerWithcomputer100timesfasterWithcomputer1000timesfaster1小时能解决的最大规模第11页，共47页，2023年，2月20日，星期三指数灾难：计算量的指数增长第12页，共47页，2023年，2月20日，星期三Non-deterministicalgorithms目前所講的算法都有一個前提假設，就是它的每個運算(operation)的結果都是獨一(確定)的。這種性質的算法可以在實際的電腦上執行，稱為deterministicalgorithms.在討論計算理論時，可以將這種限制拿掉，也就是可以假設一個運算的結果不唯一，可能是某n個結果中的一個，而且一定會是正確的那一個。這樣子的算法稱為non-deterministicalgorithm。這種算法無法在實際的電腦上執行。第13页，共47页，2023年，2月20日，星期三我們定義下列三個涵數來說明這種算法。Choice(S):從S中選一個正確的答案來(若正確答案存在的話)。Failure():沒有成功地完成工作。Success():成功地完成工作這三個涵數的執行時間都是O(1)。只有在不可能有正確答案的情形下，non-deterministicalgorithm才無法成功地完成工作。一個可以執行non-deterministicalgorithm的機器稱為non-deterministicmachine.第14页，共47页，2023年，2月20日，星期三Example1searchingA[1:n]是一個n個元素的集合，要在A中搜尋一個元素x的non-deterministicalgorithm如下：

intj=Choice(1,n); if(A[j]==x){cout<<j;Success();} cout<<‘0’;Failure();因為Choice(1,n)一定會找出一個正確的值，所以拿它找出來的值j來比較A[j]==x若不成立的話，就表示x不在A裡面。Timecomplexity是O(1)。第15页，共47页，2023年，2月20日，星期三Example2Sorting要將A[1:n]中的元素作non-decreasing的排列，non-deterministicalgorithm如下voidNsort(intA[],intn){intB[SIZE],i,j;for(i=1;i<=n;i++)B[i]=0;//初值化for(i=1;i<=n;i++){j=Choice(1,n);//選一個正確的位置if(B[j])Failure();//確認B[j]沒有被用過B[j]=A[i];}for(i=1;i<=n-1;i++)if(B[i]>B[i+1])Failure();//作確認for(i=1;i<=n;i++)cout<<B[i]<<‘‘;cout<<endl;Success();}

TimecomplexityO(n)第16页，共47页，2023年，2月20日，星期三要如何來看待non-deterministicalgorithm呢？可以用平行處理的角度來看，也就是當作同時有很多很多機器一起作同一個問題，每個機器用不同的choice的結果來作，若有一個成功的話，其他的就不用再作；若某個失敗、就自己停下來即可。另外更好的解釋是，實際上可能有一種方法可以選擇一個正確的答案出來(只要正確答案存在)，只是我們還不曉得而已（上帝知道），Choice(S)就代表可以找到S中正確答案的函數(若正確答案存在)。若正確答案不存在的話，Choice(S)還是會找出一個答案，所以我們需要確認此答案是否正確。第17页，共47页，2023年，2月20日，星期三DefinitionAnyproblemforwhichtheansweriseitherzerooroneiscalledadecision

problem.Analgorithmforadecisionproblemistermedadecision

algorithm.Anyproblemthatinvolvestheidentificationofanoptimal(eitherminimumormaximum)valueofagivencostfunctionisknownasanoptimization

problem.Anoptimization

algorithmisusedtosolveanoptimizationproblem.第18页，共47页，2023年，2月20日，星期三非确定型图灵机（NTM)猜想阶段验证阶段有限状态控制器1111110000000BBB1…………猜想模块第19页，共47页，2023年，2月20日，星期三非确定型图灵机的形式化有限状态集

有限输入符号集

有限带符号集

转移函数

开始状态

特殊带符:空白符

终态集合q0Q

T

B–T

FQ转移函数:可随机选择形式定义一个非确定型图灵机TM

是一个七元组

M=(Q,T,,,q0,B

,F).

第20页，共47页，2023年，2月20日，星期三P类 （Polynomial) P类具有多项式时间算法的判定问题形成的计算复杂性类在确定型图灵机上多项式时间可解的问题第21页，共47页，2023年，2月20日，星期三NP类(NondeterministicPolynomial)NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当第22页，共47页，2023年，2月20日，星期三CommonlybelievedrelationshipbetweenPandNP一般相信P

與NP

兩集合不相同，也就是相信有些問題是屬於NP

而不屬於P，但目前仍然無法證明。Cook曾問過一個問題：有沒有什麼問題應該屬於NP

而不屬於

P，如果該問題屬於P

的話，就表示P=NP

呢？PNP第23页，共47页，2023年，2月20日，星期三SatisfiabilityProblemGivenaBooleanformula(withvariablesandBooleanoperatorsAND,ORandNOT),isitsatisfiable?Isthereanassignmentofvalues0or1tovariablessothattheformulaevaluatesto1?ConjunctiveNormalForm(CNF)AclauseistheORofsomeliteralsABooleanformulaconsistingofseveralclausesseparatedbyANDisaCNFformulaE.g.,(a+b+c)(b’+d+e’+f)(a’+e)第24页，共47页，2023年，2月20日，星期三SatisfiabilityProblem…contd3-CNF:aCNFformulainwhicheachclausehas3literalsE.g.,(a+b+c’)(d+e’+f)(a’+f’+g)Givena3-CNFformula,isitsatisfiable?Thatis,isthereanassignment(tovariables)thatevaluatestheformulato1Thisisalsocalledthe3-CNF-SATproblem第25页，共47页，2023年，2月20日，星期三Non-deterministicsatisfiability

voidEval(cnfE,intn){intx[SIZE];for(inti=1;i<=n;i++)x[i]=Choice(0,1);if(E(x,n))Success();elseFailure;}這個演算法的timecomplexity是O(n)再加上E(x,n)的時間，計算propositionalformula值的時間與該formula的長度有關。這是第一個被證明為NP-complete

的問題。第26页，共47页，2023年，2月20日，星期三Cook自己提出一個答案，就是下面的定理。Theorem[cook]SatisfiabilityisinPifandonlyifP=NP.

satisfiability是第一個NP-complete的問題。要定義NP-hard與NP-complete之前，我們需要再定義一個名詞：reducibility.第27页，共47页，2023年，2月20日，星期三LetL1andL2beproblems.L1reducestoL2(alsowritten )ifandonlyifthereisawaytosolveL1byadeterministicpolynomialtimealgorithmusingadeterministicalgorithmthatsolvesL2inpolynomialtime.只要L2

有polynomialtime演算法，則L1

也存在polynomialtime演算法。例如L1

是從n個數字中找出最大的數字，而L2

是將n個數字中第k大的數字找出來，而L3

是將n個數字作排序，則L1

L2L3。

第28页，共47页，2023年，2月20日，星期三DefinitionAproblemLisNP-hardifandonlyifsatisfiabilityreducestoL(satisfiability ).AproblemLisNP-completeifandonlyifLisNP-hardand NP.PNPNP-hardNP-complete第29页，共47页，2023年，2月20日，星期三同一個問題的decision版本與optimization版本常常可以互相reduce，像maxclique其實reducibility還有更多種定義。Haltingproblem是一個NP-hard的問題，因為satisfiability的問題可以reduce成haltingproblem。Haltingproblem的問題是輸入一個演算法A與此A的inputI，決定A輸入I時會不會停(或者進入無窮迴圈)。這個問題是undecidable(無法決定的)，也就是不存在任何(時間複雜度的)演算法來解決這個問題，所以這個問題不屬於NP。第30页，共47页，2023年，2月20日，星期三接下來證明satisfiabilityhaltingproblem，寫一個演算法A，A的input是propositionalformulaX，若X中有n個變數，則測試2n

種組合，若其中有一種使X為true的話，A就停止；否則A就進入無窮迴圈。以這個A與X當作haltingproblem的輸入，如果haltingproblem的回答是會停，則satisfiability的答案就是yes，若haltingproblem的回答是不會停，則satisfiability就是no。因此haltingproblem若有polynomialtime演算法的話、satisfiability同樣有polynomialtime演算法。故得證。第31页，共47页，2023年，2月20日，星期三DefinitionTwoproblemsL1andL2aresaidtobepolynomiallyequivalentiff and .要證明一個問題L2

是NP-hard的話，較簡單的作法是找一個已知的NP-hard問題L1，證明 。因為reducible是有遞移性的，所以satisfiability 要證明一個NP-harddecisionproblem是NP-complete,只要找出它的polynomialtimenon-deterministicalgorithm即可第32页，共47页，2023年，2月20日，星期三NP完全问题第一个NP完全问题（Cook定理1971）可满足性问题是NP完全问题六个NP完全问题（Karp1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个第33页，共47页，2023年，2月20日，星期三一些典型的NP完全问题团问题SubsetSumSatisfiabilityHamiltonianCycleTravelingSalesperson第34页，共47页，2023年，2月20日，星期三ExampleMaximumcliqueAmaximalcompletesub-graphofagraphG=(V,E)isaclique.其clique的大小就看此clique的點數。maxcliqueproblem

是一個optimizationproblem，找出一個圖形最大的clique。這個問題也可以有decision的版本，就是G的clique之大小會不會比數字k還大。(輸入：G與k)如果optimizationproblem可以g(n)的時間內作出來，則decision版本也可以在g(n)時間內作好。如果decision版本可以f(n)時間內完成，則optimization版本可以在nf(n)(?)的時間內完成。所以兩者一定同時為polynomialtime或同時不為polynomialtime。第35页，共47页，2023年，2月20日，星期三ExampleMaxclique

voidDCK(intG[][SIZE],intn,intk){S=Φ;for(inti=1;i<=k;i++){intt=Choice(1,n);if(tisinS)Failure();S=S∪{t};}for(allpairs(i,j)suchthatiisinS,jisinSandi!=j)if((i,j)isnotanedgeofG)Failure();Success();}Non-deterministiccliquepseudocode第36页，共47页，2023年，2月20日，星期三Satisfiability令x1,x2,…

代表booleanvariables，而代表xi

的相反。Aformula是這些布林變數與logicAND、logicOR的組合。Conjunctivenormalform(CNF)Disjunctivenormalform(DNF)Thesatisfiabilityproblemistodeterminewhetheraformulaistrueforsomeassignmentoftruthvaluestothevariables.CNF-satisfiability第37页，共47页，2023年，2月20日，星期三Non-deterministicsatisfiability

voidEval(cnfE,intn){intx[SIZE];for(inti=1;i<=n;i++)x[i]=Choice(0,1);if(E(x,n))Success();elseFailure;}這個演算法的timecomplexity是O(n)再加上E(x,n)的時間，計算propositionalformula值的時間與該formula的長度有關。這是第一個被證明為NP-complete

的問題。第38页，共47页，2023年，2月20日，星期三GraphColoringProblemGivenagraph,howtocolorverticessothatadjacentoneshavedifferentcolorsChromaticnumberisthesmallestnumberofcolorsneededtocoloragraphThegraphcoloringproblemOptimizationproblem:GivenagraphG=(V,E),findthechromaticnumberDecisionproblem:GivenagraphG=(V,E)andanintegerk,isGk-colorable?第39页，共47页，2023年，2月20日，星期三SubsetSumProblemGivenasetSofpositiveintegersandanintegerk