計算理論導引w2時間復雜性a np及證明

1計算理論第7章時間復雜性2引言Church-Turing論題：能夠用總停機的Turing機計算的函數(shù)和識別的語言是可計算的（可判定的）；理論可計算計算復雜性理論研究計算模型在各種資源（主要是時間、空間等）限制下的計算能力；

實際可計算一個可以計算的問題需要多少時間和空間？64層次梵塔，1秒鐘移動1000片（計算機作），要多少時間？(264-1)/1000=5.846億年3引言復雜度和時間：每秒作106的基本運算需要的時間N=10N=20N=30N=40N=50N=60N10-5秒2*10-5秒3*10-5秒4*10-5秒5*10-5秒6*10-5秒N210-4秒4*10-4秒9*10-4秒16*10-525*10-436*10-4N310-3秒8*10-3秒27*10-4秒64*10-30.125秒0.216秒N510-1秒3.224秒1.7分5.2分13分2N10-3秒118.9分12.7天35.7年366世紀3N0.059秒58分6.5年3855世紀2億世紀1.3*1013世紀4引言Complexity：Hamilton回路問題（HC）：任給一個無向圖G，問G中有Hamilton回路嗎？Hamilton回路是指經(jīng)過每一個頂點且每一個頂點只經(jīng)過一次的回路。設G有n個頂點，由于回路沒有始點和終點，可以任意定一個頂點作為排列的第一個頂點，共有（n-1）！個排列。當n=25時，24！=6.2*1023.假設用一臺超級計算機計算，每秒可以檢查1億個排列。每年有3.15*107秒，不停地工作，每年可以檢查3.15*1015個排列。檢查完所有的排列需要1.97*108年，即1億9千7百年！計算復雜性理論就是要研究計算模型在各種資源限制下的計算能力。將問題劃分成HardandEasy兩大類。5主要內(nèi)容7.1度量復雜性 大O和小o記法、分析算法、模型間的復雜性關系7.2P類 多項式時間、P中的問題舉例7.3NP類

NP中的問題舉例、P與NP問題7.4NP完全性 多項式時間可歸約性、NP完全性的定義、庫克-列文定理7.5幾個NP完全問題（自學） 頂點覆蓋問題、哈密頓路徑問題、子集和問題6度量復雜性考察下列例子： 語言A={0k1k|k

≥0}，顯然A是一個可判定的語言。 考察下面判定A的單帶TMM1

M1=“對于輸入串w：1)掃描帶子，如果在1的右邊發(fā)現(xiàn)0，就拒絕。2)如果帶上既有0也有1，就重復下一步。3)掃描帶子，刪除一個0和一個1。4)如果所有1都被刪除以后還有0，或者所有0都被刪除以后還有1，就拒絕。否則，如果在帶上既沒有剩下0也沒有剩下1，就接受。考察判定A的圖靈機M1的算法所需的時間。7度量復雜性把算法的運行時間純粹作為表示輸入字符串的長度來計算，而不考慮其它參數(shù)。最壞情況分析（worst-caseanalysis）：考慮在某特定長度的所有輸入上的最長運行時間。平均情況分析（average-caseanalysis）：考慮在某特定長度的所有輸入上的運行時間的平均值。8度量復雜性定義8.1令M是一個在所有輸入上都停機的確定型圖靈機。M的運行時間或者時間復雜度，是一個函數(shù)

f:N

N，其中N是非負整數(shù)集合，f(n)是M在所有長度為n的輸入上運行時所經(jīng)過的最大步數(shù)。若f(n)是M的運行時間，則稱M在時間f(n)內(nèi)運行，M是時間圖靈機。通常使用n表示輸入的長度。9漸進分析因為算法的精確運行時間通常是一個復雜的表達式，所以一般是估計它的趨勢和級別。通過一種稱為漸進分析

(asymptoticanalysis)的方便的估計形式，可以試圖了解算法在長輸入上的運行時間。只考慮算法運行時間的表達式的最高項，而忽略該項的系數(shù)和其它低次項，因為在在長輸入上，最高次項的影響相比其它項占據(jù)主導地位。例如，函數(shù)f(n)=6n3+2n2+20n+45

稱f漸進地不大于n3，表達這種關系的漸進記法或大O記法是f(n)=O(n3)。10大O和小o記法定義8.2設f和g

是兩個函數(shù)f，g：N

R+。稱f(n)=O(g(n))，若存在正整數(shù)c和

n0，使得對所有

n≥n0

有f(n)≤cg(n)當f(n)=O(g(n))時，稱g(n)是f(n)的上界，或更準確地說，

g(n)是f(n)的漸近上界，以強調(diào)沒有考慮常數(shù)因子。11大O和小o記法例8.3

f1(n)是函數(shù)5n3+2n2+22n+6。保留最高次項5n3，并且舍去它的系數(shù)5，得到f1=O(n3)。驗證該結果是否滿足上面的形式定義。令c=6，n0=10，則對于所有n

≥10，有5n3+2n2+22n+6≤6n3。此外，有f1=O(n4)，因為n4比n3大，它也是f1的一個漸近上界。但是f1不等于O(n2)，不論給c和n0賦什么值，始終不滿足定義的要求。12大O和小o記法例8.4

大O記法以一種特別的方式與對數(shù)相互影響。通常寫對數(shù)時必須指明基數(shù)(或稱為對數(shù)的底)，如x=log2n

。這里基數(shù)2表明該等式等價于等式2x=n。logbn的值隨著基數(shù)b的改變而乘以相應的常數(shù)倍，因為有恒等式logbn=log2n/log2b。所以，寫f(n)=O(logn)

時不必再指明基數(shù)，因為最終要忽略常數(shù)因子。13大O和小o記法令f2(n)是函數(shù)3nlog2n+5nlog2log2n+2。此時f2(n)

=O(nlogn)，因為

logn比loglogn更占支配位置。f(n)

=O(n2)+O(n)等價于f(n)

=O(n2)當O出現(xiàn)在指數(shù)位置，如f(n)=2O(n)，代表著2cn的一個上界。f(n)=2O(logn)，代表nc。（由n=2logn

得nc=2clog2n）2O(1)代表了同樣的界，因為表達式O(1)代表不超過某個固定常數(shù)的上界。14大O和小o記法我們經(jīng)常導出nc

的界，c是大于0的常數(shù)。這種界稱為多項式界(polynamialbound)。形如的界，當是大于0的實數(shù)時，稱為指數(shù)界(exponentialbound)。大O記法指一個函數(shù)漸近地不大于另一個函數(shù)。小o記法是漸進的小于另一個函數(shù)。大O記法與小o記法的區(qū)別類似于≤和＜之間的區(qū)別。15大O和小o記法定義8.5設f和g是兩個函數(shù)f,g:N

R+，如果則稱f(n)=o(g(n))。換言之，f(n)=o(g(n))意味著對于任何實數(shù)c＞0，存在一個數(shù)n0，使得對所有n≥n0，f(n)＜cg(n)。16大O和小o記法例8.6

容易驗證下面的等式。

1)