計(jì)算理論導(dǎo)引_7_時(shí)間復(fù)雜性

1、1樸秀峰樸秀峰計(jì)算理論2引言q Church-Turing論題論題：能夠用總停機(jī)的：能夠用總停機(jī)的Turing機(jī)計(jì)算的函數(shù)機(jī)計(jì)算的函數(shù)和識(shí)別的語(yǔ)言是可計(jì)算的（可判定的）；和識(shí)別的語(yǔ)言是可計(jì)算的（可判定的）；理論可計(jì)算理論可計(jì)算q 計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論研究計(jì)算模型在各種資源（主要是研究計(jì)算模型在各種資源（主要是時(shí)間時(shí)間、空間空間等）限制下的計(jì)算能力；等）限制下的計(jì)算能力； 實(shí)際可計(jì)算實(shí)際可計(jì)算q 一個(gè)可以計(jì)算的問(wèn)題一個(gè)可以計(jì)算的問(wèn)題 需要多少時(shí)間和空間？需要多少時(shí)間和空間？q 64層次梵塔，層次梵塔，1秒鐘移動(dòng)秒鐘移動(dòng)1000片（計(jì)算機(jī)作），要多少時(shí)間？片（計(jì)算機(jī)作），要多少時(shí)間？q (

2、 264-1) / 1000=5.846 億年億年3引言q 復(fù)雜度和時(shí)間復(fù)雜度和時(shí)間 ：每秒作：每秒作106的基本運(yùn)算需要的時(shí)間的基本運(yùn)算需要的時(shí)間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秒秒117.9分分12.7天天35.7年年366世紀(jì)世紀(jì)3

3、N0.059秒秒58分分6.5年年3855世世紀(jì)紀(jì)2億世紀(jì)億世紀(jì)1.3*1013世紀(jì)世紀(jì)4引言Complexity：Hamilton回路問(wèn)題（回路問(wèn)題（HC）：任給一個(gè)無(wú)向圖）：任給一個(gè)無(wú)向圖G，問(wèn)，問(wèn)G中有中有Hamilton回路嗎？回路嗎？Hamilton回路是指經(jīng)過(guò)每一個(gè)頂點(diǎn)且每一個(gè)頂點(diǎn)只經(jīng)過(guò)一次的回路。回路是指經(jīng)過(guò)每一個(gè)頂點(diǎn)且每一個(gè)頂點(diǎn)只經(jīng)過(guò)一次的回路。q 設(shè)設(shè)G有有n個(gè)頂點(diǎn)，由于回路沒(méi)有始點(diǎn)和終點(diǎn)，可以任意定一個(gè)頂點(diǎn)作為排列的個(gè)頂點(diǎn)，由于回路沒(méi)有始點(diǎn)和終點(diǎn)，可以任意定一個(gè)頂點(diǎn)作為排列的第一個(gè)頂點(diǎn)，共有（第一個(gè)頂點(diǎn)，共有（n-1）！個(gè)排列。當(dāng)）！個(gè)排列。當(dāng)n=25時(shí)，時(shí)，24！=6.2

4、*1023.假設(shè)用一臺(tái)超假設(shè)用一臺(tái)超級(jí)計(jì)算機(jī)計(jì)算，每秒可以檢查級(jí)計(jì)算機(jī)計(jì)算，每秒可以檢查1億個(gè)排列。每年有億個(gè)排列。每年有3.15*107秒，不停地工作，秒，不停地工作，每年可以檢查每年可以檢查3.15*1015個(gè)排列。檢查完所有的排列需要個(gè)排列。檢查完所有的排列需要1.97*108年，即年，即1億億9千千7百年！百年！q 計(jì)算復(fù)雜性理論就是要研究計(jì)算模型在各種資源限制下的計(jì)算能力。將問(wèn)題劃計(jì)算復(fù)雜性理論就是要研究計(jì)算模型在各種資源限制下的計(jì)算能力。將問(wèn)題劃分成分成Hard and Easy 兩大類(lèi)。兩大類(lèi)。5引言co-TM recognizable（補(bǔ)集可識(shí)）TM-recognizable

5、TM decidable PSPACE co-NPNP P6主要內(nèi)容主要內(nèi)容7.1 度量復(fù)雜性度量復(fù)雜性大大 O 和小和小 o 記法、分析算法、模型間的復(fù)雜性關(guān)系記法、分析算法、模型間的復(fù)雜性關(guān)系7.2 P類(lèi)類(lèi)多項(xiàng)式時(shí)間、多項(xiàng)式時(shí)間、P 中的問(wèn)題舉例中的問(wèn)題舉例7.3 NP類(lèi)類(lèi)NP中的問(wèn)題舉例、中的問(wèn)題舉例、P 與與 NP 問(wèn)題問(wèn)題7.4 NP完全性完全性多項(xiàng)式時(shí)間可歸約性、多項(xiàng)式時(shí)間可歸約性、NP 完全性的定義、庫(kù)克完全性的定義、庫(kù)克-列文定理列文定理7.5 幾個(gè)幾個(gè)NP完全問(wèn)題完全問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題7度量復(fù)雜性q 考察下列例

6、子：考察下列例子：語(yǔ)言語(yǔ)言 A = 0k1k | k 0 ，顯然，顯然 A 是一個(gè)可判定的語(yǔ)言。是一個(gè)可判定的語(yǔ)言?？疾煜旅媾卸疾煜旅媾卸ˋ的單帶的單帶 TM M1M1=“對(duì)于輸入串對(duì)于輸入串 w：1) 掃描帶子，如果在掃描帶子，如果在 1 的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn) 0，就，就拒絕拒絕。2) 如果帶上既有如果帶上既有 0 也有也有 1，就重復(fù)下一步。，就重復(fù)下一步。3) 掃描帶子，刪除一個(gè)掃描帶子，刪除一個(gè) 0 和一個(gè)和一個(gè) 1。4) 如果所有如果所有 1 都被刪除以后還有都被刪除以后還有 0，或者所有，或者所有 0 都被刪除以后還有都被刪除以后還有 1，就，就拒絕拒絕。否則，如果在帶上既沒(méi)有剩

7、下。否則，如果在帶上既沒(méi)有剩下0也沒(méi)有剩下也沒(méi)有剩下 1，就，就接受接受。q 考察判定考察判定 A 的圖靈機(jī)的圖靈機(jī) M1 的算法所需的時(shí)間。的算法所需的時(shí)間。8度量復(fù)雜性q 把把算法的運(yùn)行時(shí)間算法的運(yùn)行時(shí)間純粹作為表示純粹作為表示輸入字符串的長(zhǎng)度輸入字符串的長(zhǎng)度來(lái)計(jì)算，來(lái)計(jì)算，而不考慮其它參數(shù)。而不考慮其它參數(shù)。q 最壞情況分析（最壞情況分析（worst-case analysis）：考慮在某特定長(zhǎng)度：考慮在某特定長(zhǎng)度的所有輸入上的最長(zhǎng)運(yùn)行時(shí)間。的所有輸入上的最長(zhǎng)運(yùn)行時(shí)間。q 平均情況分析（平均情況分析（average-case analysis）：考慮在某特定長(zhǎng)：考慮在某特定長(zhǎng)度的所有輸入

8、上的運(yùn)行時(shí)間的平均值。度的所有輸入上的運(yùn)行時(shí)間的平均值。9度量復(fù)雜性令令 M 是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。M 的的運(yùn)行時(shí)間運(yùn)行時(shí)間或者或者時(shí)間復(fù)雜度時(shí)間復(fù)雜度，是一個(gè)函數(shù)，是一個(gè)函數(shù) f : N N，其中，其中 N 是非負(fù)整數(shù)集合，是非負(fù)整數(shù)集合， f(n) 是是 M 在在所有長(zhǎng)度為所有長(zhǎng)度為 n 的輸入上運(yùn)行時(shí)所經(jīng)過(guò)的最大步數(shù)的輸入上運(yùn)行時(shí)所經(jīng)過(guò)的最大步數(shù)。若若 f(n) 是是 M 的運(yùn)行時(shí)間，則稱(chēng)的運(yùn)行時(shí)間，則稱(chēng) M 在時(shí)間在時(shí)間 f(n) 內(nèi)運(yùn)內(nèi)運(yùn)行，行，M 是時(shí)間圖靈機(jī)。是時(shí)間圖靈機(jī)。通常使用通常使用 n 表示輸入的長(zhǎng)度。表示輸入的長(zhǎng)

9、度。10漸進(jìn)分析q 因?yàn)樗惴ǖ木_運(yùn)行時(shí)間通常是一個(gè)復(fù)雜的表達(dá)式，所以因?yàn)樗惴ǖ木_運(yùn)行時(shí)間通常是一個(gè)復(fù)雜的表達(dá)式，所以一般是估計(jì)它的趨勢(shì)和級(jí)別。一般是估計(jì)它的趨勢(shì)和級(jí)別。q 通過(guò)一種稱(chēng)為通過(guò)一種稱(chēng)為漸進(jìn)分析漸進(jìn)分析 (asymptotic analysis) 的方便的估計(jì)的方便的估計(jì)形式，可以試圖了解算法在長(zhǎng)輸入上的運(yùn)行時(shí)間。形式，可以試圖了解算法在長(zhǎng)輸入上的運(yùn)行時(shí)間。q 只考慮算法運(yùn)行時(shí)間的表達(dá)式的最高項(xiàng)，而忽略該項(xiàng)的系只考慮算法運(yùn)行時(shí)間的表達(dá)式的最高項(xiàng)，而忽略該項(xiàng)的系數(shù)和其它低次項(xiàng)，因?yàn)樵谠陂L(zhǎng)輸入上，數(shù)和其它低次項(xiàng)，因?yàn)樵谠陂L(zhǎng)輸入上，最高次項(xiàng)最高次項(xiàng)的影響相的影響相比其它項(xiàng)比其它項(xiàng)占據(jù)主

10、導(dǎo)地位占據(jù)主導(dǎo)地位。q 例如，函數(shù)例如，函數(shù) f (n) = 6n3+2n2+20n+45稱(chēng)稱(chēng) f 漸進(jìn)地不大于漸進(jìn)地不大于 n3，表達(dá)這種關(guān)系的，表達(dá)這種關(guān)系的漸進(jìn)記法漸進(jìn)記法或大或大 O 記記法法是是 f (n) = O(n3)。 11大 O 和小 o記法設(shè)設(shè) f 和和 g 是兩個(gè)函數(shù)是兩個(gè)函數(shù) f ，g： N R+。稱(chēng)。稱(chēng)f(n)=O(g(n)，若存在正整數(shù)，若存在正整數(shù) c 和和 n0，使得對(duì)所有，使得對(duì)所有 nn0 有有f(n) cg(n)當(dāng)當(dāng) f(n)=O(g(n) 時(shí)，稱(chēng)時(shí)，稱(chēng) g(n) 是是 f(n) 的的上界上界，或更準(zhǔn)，或更準(zhǔn)確地說(shuō)，確地說(shuō)， g(n)是是 f(n)的漸近上

11、界，的漸近上界，以強(qiáng)調(diào)沒(méi)有考慮以強(qiáng)調(diào)沒(méi)有考慮常數(shù)因子。常數(shù)因子。12大 O 和小 o 記法例例7.3 f1(n) 是函數(shù)是函數(shù) 5n3+2n2+22n+6。保留最高次項(xiàng)。保留最高次項(xiàng) 5n3，并且，并且舍去它的系數(shù)舍去它的系數(shù)5，得到，得到 f1=O(n3)。驗(yàn)證該結(jié)果是否滿(mǎn)足上面的形式定義。驗(yàn)證該結(jié)果是否滿(mǎn)足上面的形式定義。令令c=6，n0=10，則對(duì)，則對(duì)于所有于所有n 10，有，有 5n3+2n2+22n+6 6n3。此外，有此外，有 f1=O(n4)，因?yàn)?，因?yàn)?n4 比比 n3 大，它也是大，它也是 f1 的一個(gè)漸近上的一個(gè)漸近上界。界。但是但是 f1 不等于不等于 O(n2)，不論

12、給，不論給 c 和和 n0 賦什么值，始終不滿(mǎn)足賦什么值，始終不滿(mǎn)足定義的要求。定義的要求。13大 O 和小 o 記法例例7.4 大大O記法以一種特別的方式與對(duì)數(shù)相互影響。記法以一種特別的方式與對(duì)數(shù)相互影響。通常通常寫(xiě)對(duì)數(shù)時(shí)必須指明基數(shù)寫(xiě)對(duì)數(shù)時(shí)必須指明基數(shù)(或稱(chēng)為對(duì)數(shù)的底或稱(chēng)為對(duì)數(shù)的底)，如，如 x=log2n 。這里基數(shù)這里基數(shù) 2 表明表明該等式等價(jià)于等式該等式等價(jià)于等式 2x=n。logbn 的的值值隨著基數(shù)隨著基數(shù) b 的的改變而乘以相應(yīng)的常數(shù)倍，因?yàn)楦淖兌艘韵鄳?yīng)的常數(shù)倍，因?yàn)橛泻愕仁接泻愕仁?logbn = log2n / log2b。所以，寫(xiě)。所以，寫(xiě) f(n) = O(logn

13、) 時(shí)時(shí)不必再指明基數(shù)，因?yàn)椴槐卦僦该骰鶖?shù)，因?yàn)樽罱K最終要忽略常數(shù)因子。要忽略常數(shù)因子。14大 O 和小 o 記法q 令令 f2(n) 是函數(shù)是函數(shù) 3nlog2n+5nlog2log2n+2。 此時(shí)此時(shí) f2(n) =O(nlogn)，因?yàn)椋驗(yàn)?logn 比比 log logn更占支配位置。更占支配位置。q f(n) =O(n2)+ O(n) 等價(jià)于等價(jià)于 f(n) =O(n2)q 當(dāng)當(dāng) O 出現(xiàn)在指數(shù)位置，如出現(xiàn)在指數(shù)位置，如 f(n) =2O(n)，代表著，代表著 2cn 的一個(gè)上的一個(gè)上界。界。q f(n) =2O(logn)，代表，代表 nc。（由。（由 n = 2log n 得得

14、 nc = 2c log 2n）q 2O(1) 代表了同樣的界，因?yàn)楸磉_(dá)式代表了同樣的界，因?yàn)楸磉_(dá)式 O(1) 代表不超過(guò)某個(gè)固代表不超過(guò)某個(gè)固定常數(shù)的上界。定常數(shù)的上界。15大O 和小o 記法q 我們經(jīng)常導(dǎo)出我們經(jīng)常導(dǎo)出 nc 的界，的界，c 是大于是大于 0 的常數(shù)。這種界稱(chēng)為的常數(shù)。這種界稱(chēng)為多多項(xiàng)式界項(xiàng)式界 (polynamial bound)。形如。形如 的界，當(dāng)?shù)慕?，?dāng) 是大于是大于 0的實(shí)數(shù)時(shí)，稱(chēng)為的實(shí)數(shù)時(shí)，稱(chēng)為指數(shù)界指數(shù)界(exponential bound)。q 大大 O 記法記法指一個(gè)函數(shù)漸近地指一個(gè)函數(shù)漸近地不大于不大于另一個(gè)函數(shù)。另一個(gè)函數(shù)。q 小小 o 記法記法是漸進(jìn)

15、的是漸進(jìn)的小于小于另一個(gè)函數(shù)。另一個(gè)函數(shù)。q 大大O記法與小記法與小o記法的區(qū)別類(lèi)似于記法的區(qū)別類(lèi)似于和之間的區(qū)別。和之間的區(qū)別。2n16大O 和小o 記法設(shè)設(shè) f 和和 g 是兩個(gè)函數(shù)是兩個(gè)函數(shù) f , g : N R+，如果，如果則稱(chēng)則稱(chēng) f (n) = o(g(n)。換言之，。換言之，f (n) = o(g(n) 意味著意味著對(duì)于任何實(shí)數(shù)對(duì)于任何實(shí)數(shù) c0，存在一個(gè)數(shù)，存在一個(gè)數(shù) n0，使得對(duì)所有，使得對(duì)所有 nn0，f (n)cg(n)。( )lim0( )nf ng n17大O 和小o 記法例例7.6 容易驗(yàn)證下面的等式。容易驗(yàn)證下面的等式。 1) 2) n = o(nlog(log

16、n) 3) nlog(logn) = o(nlogn) 4) nlogn = o(n2) 5) n2 = o(n3) 但是，但是，f(n) 不會(huì)等于不會(huì)等于o(f(n) 。( )no n18分析算法分析語(yǔ)言分析語(yǔ)言 A = 0k1k | k 0 對(duì)應(yīng)的圖靈機(jī)算法。對(duì)應(yīng)的圖靈機(jī)算法。M1 = “對(duì)于輸入串對(duì)于輸入串 w：1) 掃描帶子，如果在掃描帶子，如果在 1 的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn) 0，就，就拒絕拒絕。2) 如果帶上既有如果帶上既有 0 也有也有 1，就重復(fù)下一步。，就重復(fù)下一步。3) 掃描帶子，刪除一個(gè)掃描帶子，刪除一個(gè) 0 和一個(gè)和一個(gè) 1。4) 如果所有如果所有 1 都被刪除以后還有都被

17、刪除以后還有 0，或者所有，或者所有 0 都被刪除以后還有都被刪除以后還有 1，就就拒絕拒絕。否則，如果在帶上既沒(méi)有剩下。否則，如果在帶上既沒(méi)有剩下 0 也沒(méi)有剩下也沒(méi)有剩下 1，就，就接受接受。 q 步驟步驟1中，機(jī)器掃描帶以驗(yàn)證輸入的形式是中，機(jī)器掃描帶以驗(yàn)證輸入的形式是0*1*。執(zhí)行這次掃描需要。執(zhí)行這次掃描需要n步步。讀寫(xiě)頭重新放置在帶的左端另外需要讀寫(xiě)頭重新放置在帶的左端另外需要n步步。共需要。共需要2n步步。即。即O(n)步。步。q 在步驟在步驟2和和3中，機(jī)器反復(fù)掃描帶，在每一次掃描中刪除一個(gè)中，機(jī)器反復(fù)掃描帶，在每一次掃描中刪除一個(gè)0和一個(gè)和一個(gè)1。每一次掃描需要每一次掃描需要

18、O(n)步步。因?yàn)槊恳淮螔呙鑴h除兩個(gè)符號(hào)，所以。因?yàn)槊恳淮螔呙鑴h除兩個(gè)符號(hào)，所以最多掃描最多掃描n/2次次。于是步驟。于是步驟2和和3需要的全部時(shí)間是需要的全部時(shí)間是(n/2)O(n)=O(n2)步。步。q 在步驟在步驟4中，機(jī)器掃描一次來(lái)決定是接受還是拒絕。最多需要中，機(jī)器掃描一次來(lái)決定是接受還是拒絕。最多需要O(n)步。步。q 所以，所以，M1在長(zhǎng)度為在長(zhǎng)度為n的輸入上總共耗時(shí)為的輸入上總共耗時(shí)為O(n)+O(n2)+O(n)，或，或O(n2)。換。換言之，它的言之，它的運(yùn)行時(shí)間是運(yùn)行時(shí)間是O(n2)。19時(shí)間復(fù)雜性類(lèi)令令 t : N R+ 是一個(gè)函數(shù)。定義是一個(gè)函數(shù)。定義時(shí)間復(fù)雜性類(lèi)時(shí)間

19、復(fù)雜性類(lèi)TIME(t(n) 為由為由 O(t(n) 時(shí)間的圖靈機(jī)判定的時(shí)間的圖靈機(jī)判定的所有所有語(yǔ)言的集合語(yǔ)言的集合。語(yǔ)言語(yǔ)言 A = 0k1k | k0 ，ATIME(n2)，因?yàn)橐驗(yàn)?M1 在時(shí)間在時(shí)間 O(n2) 內(nèi)判定內(nèi)判定 A，而，而 TIME(n2) 包括所有在時(shí)間包括所有在時(shí)間內(nèi)可判定的語(yǔ)言。內(nèi)可判定的語(yǔ)言。是否存在漸近更快地判定是否存在漸近更快地判定 A 的機(jī)器呢？的機(jī)器呢？在每次掃描中刪除兩個(gè)在每次掃描中刪除兩個(gè) 0 和兩個(gè)和兩個(gè) 1，如何？，如何？20分析 M2 的時(shí)間復(fù)雜性q 下面機(jī)器下面機(jī)器 M2 采用不同的方法，可以更快地判定采用不同的方法，可以更快地判定 A。ATI

20、ME(nlogn)。M2=“對(duì)輸入串對(duì)輸入串 w：1) 掃描帶，如果掃描帶，如果 1 的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn) 0，就，就拒絕拒絕。2) 只要在帶上還有只要在帶上還有 0 和和 1，就重復(fù)下面的步驟。，就重復(fù)下面的步驟。3) 掃描帶，檢查剩余的掃描帶，檢查剩余的 0 和和 1 的總數(shù)是偶數(shù)還是奇數(shù)。的總數(shù)是偶數(shù)還是奇數(shù)。 若是奇數(shù)，就若是奇數(shù)，就拒絕拒絕。4) 再次掃描帶，從第一個(gè)再次掃描帶，從第一個(gè) 0 開(kāi)始，開(kāi)始，隔一個(gè)刪除一個(gè)隔一個(gè)刪除一個(gè) 0； 然后從第一個(gè)然后從第一個(gè) 1 開(kāi)始，開(kāi)始，隔一個(gè)刪除一個(gè)隔一個(gè)刪除一個(gè) 1.5) 如果帶上不再有如果帶上不再有 0 和和 1，就，就接受接受。否則

21、。否則拒絕拒絕?！眖 首先注意，每一步都消耗首先注意，每一步都消耗 O(n) 的時(shí)間。的時(shí)間。q 步驟步驟1和和5執(zhí)行一次，共需要執(zhí)行一次，共需要O(n)時(shí)間。時(shí)間。q 步驟步驟4在每一次執(zhí)行時(shí)至少刪除一半的在每一次執(zhí)行時(shí)至少刪除一半的0和和1，所以至多，所以至多1+log2n次循環(huán)就可次循環(huán)就可以把全部字符刪除。于是，步驟以把全部字符刪除。于是，步驟2、3和和4總共消耗時(shí)間總共消耗時(shí)間(1+log2n) O(n)，即，即O(nlogn)。M2的運(yùn)行時(shí)間是的運(yùn)行時(shí)間是O(n) +O(nlogn)= O(nlogn)。 q ATIME(nlogn)。這個(gè)結(jié)果在單帶圖靈機(jī)上不可能進(jìn)一步改進(jìn)。這個(gè)結(jié)

22、果在單帶圖靈機(jī)上不可能進(jìn)一步改進(jìn)。q 單帶圖靈機(jī)在單帶圖靈機(jī)在o(nlogn)時(shí)間內(nèi)判定的語(yǔ)言都是正則語(yǔ)言時(shí)間內(nèi)判定的語(yǔ)言都是正則語(yǔ)言。21分析M3的時(shí)間復(fù)雜性q 如果圖靈機(jī)有第二條帶，就可以在如果圖靈機(jī)有第二條帶，就可以在O(n)時(shí)間（也稱(chēng)為線(xiàn)性時(shí)間）內(nèi)判定時(shí)間（也稱(chēng)為線(xiàn)性時(shí)間）內(nèi)判定語(yǔ)言語(yǔ)言A。下面的兩帶圖靈機(jī)。下面的兩帶圖靈機(jī)TM M3在線(xiàn)性時(shí)間內(nèi)判定在線(xiàn)性時(shí)間內(nèi)判定A。M3 = “ 對(duì)于輸入串對(duì)于輸入串 w：1) 掃描帶，如果掃描帶，如果 1 的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn) 0，就，就拒絕拒絕。2) 掃描帶掃描帶 1 上的上的 0，直到第一個(gè)，直到第一個(gè) 1 時(shí)停止，同時(shí)把時(shí)停止，同時(shí)把 0 復(fù)

23、制到帶復(fù)制到帶 2 上。上。3) 掃描帶掃描帶 1 上的上的 1 直到輸入的末尾。每次從帶直到輸入的末尾。每次從帶 1 上讀到一個(gè)上讀到一個(gè) 1，就在帶，就在帶 2 上刪除一個(gè)上刪除一個(gè) 0，如果在讀完，如果在讀完 1 之前所有的之前所有的 0 都被刪除，就都被刪除，就拒絕拒絕。4) 如果所有如果所有 0 都被刪除，就都被刪除，就接受接受。如果還有。如果還有 0 剩下，就剩下，就拒絕拒絕?！眖 四個(gè)步驟中每一步需要四個(gè)步驟中每一步需要O(n)步，所以全部的運(yùn)行時(shí)間是步，所以全部的運(yùn)行時(shí)間是O(n)，因而是，因而是線(xiàn)性的。線(xiàn)性的。q 注意，這可能是最好的運(yùn)行時(shí)間，因?yàn)楣馐亲x輸入就需要注意，這可能

24、是最好的運(yùn)行時(shí)間，因?yàn)楣馐亲x輸入就需要n步。步。22A 的 C 程序A = 0k1k | k=0,1,2, . 先用用C語(yǔ)言寫(xiě)程序判斷串 s 是否 0k1k Bool M(char *s) int L=strlen(s) /掃描一遍 O(n) if (L%2)!=0 return false; /長(zhǎng)度不是偶數(shù) else N=L/2; for( k=1;kN; k+) / if (sk !=0) return false; /O(n) if (sk+N!=1) return false; /相當(dāng)于第二條帶 O(n) return true; 判斷一個(gè)串，用 O(n)時(shí)間. 使用的資源:隨機(jī)存取,

25、數(shù)組，兩帶圖靈機(jī)，23總結(jié) A 的運(yùn)行時(shí)間q 給出一個(gè)單帶給出一個(gè)單帶 TM M1，能夠在時(shí)間，能夠在時(shí)間 O(n2)內(nèi)判定內(nèi)判定A，以及一，以及一個(gè)更快的單帶個(gè)更快的單帶 TM M2，能夠在時(shí)間，能夠在時(shí)間 O(nlogn)內(nèi)判定內(nèi)判定A。兩。兩帶帶 TM M3 能在能在 O(n) 時(shí)間內(nèi)判定語(yǔ)言時(shí)間內(nèi)判定語(yǔ)言A。q 因此因此 A 在單帶在單帶 TM 上的時(shí)間復(fù)雜度是上的時(shí)間復(fù)雜度是 O(nlogn)，在兩帶，在兩帶TM 上是上是 O(n)。q 注意注意 A 的復(fù)雜度與選擇的計(jì)算模型有關(guān)。的復(fù)雜度與選擇的計(jì)算模型有關(guān)。24復(fù)雜性理論與可計(jì)算性理論的區(qū)別q 在在可計(jì)算性理論可計(jì)算性理論中，丘奇

26、中，丘奇-圖靈論題斷言，圖靈論題斷言，所有合理的計(jì)算所有合理的計(jì)算模型都是等價(jià)的模型都是等價(jià)的，即它們所判定的語(yǔ)言類(lèi)都是相同的。，即它們所判定的語(yǔ)言類(lèi)都是相同的。q 在在復(fù)雜性理論復(fù)雜性理論中，中，模型的選擇影響語(yǔ)言的時(shí)間復(fù)雜度模型的選擇影響語(yǔ)言的時(shí)間復(fù)雜度。如。如在一個(gè)模型上線(xiàn)性時(shí)間內(nèi)可判定的語(yǔ)言，在另一個(gè)模型上在一個(gè)模型上線(xiàn)性時(shí)間內(nèi)可判定的語(yǔ)言，在另一個(gè)模型上就不一定是線(xiàn)性時(shí)間內(nèi)可判定的。就不一定是線(xiàn)性時(shí)間內(nèi)可判定的。q 在復(fù)雜性理論中，在復(fù)雜性理論中，根據(jù)計(jì)算問(wèn)題的時(shí)間復(fù)雜度來(lái)對(duì)問(wèn)題分根據(jù)計(jì)算問(wèn)題的時(shí)間復(fù)雜度來(lái)對(duì)問(wèn)題分類(lèi)類(lèi)。25模型間的復(fù)雜性關(guān)系設(shè)設(shè) t(n) 是一個(gè)函數(shù)，是一個(gè)函數(shù)，

27、t(n)n。則每一個(gè)時(shí)間。則每一個(gè)時(shí)間 t(n)的的多帶多帶圖靈機(jī)都和某一個(gè)圖靈機(jī)都和某一個(gè) O(t2(n) 時(shí)間的時(shí)間的單帶單帶圖靈機(jī)圖靈機(jī)等價(jià)。等價(jià)。S 用它的一條帶表示用它的一條帶表示 M 的所有的所有k條帶條帶的內(nèi)容。這些帶連續(xù)存放，的內(nèi)容。這些帶連續(xù)存放， M 的讀的讀寫(xiě)頭的位置都標(biāo)在恰當(dāng)?shù)姆礁裆稀?xiě)頭的位置都標(biāo)在恰當(dāng)?shù)姆礁裆稀?1010Maaa ba #01010#aaa#ba# S26模型間的復(fù)雜性關(guān)系01010Maaa ba #01010#aaa#ba# S開(kāi)始時(shí)，開(kāi)始時(shí)， S 讓它的帶形成表示讓它的帶形成表示 M 的所有帶的格式，然后模擬的所有帶的格式，然后模擬 M 的步驟。

28、的步驟。為了模擬為了模擬 M 的一步，的一步， S 掃描帶上的所有信息，掃描帶上的所有信息，確定在確定在 M 的讀寫(xiě)頭下的符的讀寫(xiě)頭下的符號(hào)號(hào)。然后。然后 S 再次掃描帶，再次掃描帶，更新帶內(nèi)容和讀寫(xiě)頭位置更新帶內(nèi)容和讀寫(xiě)頭位置。如果。如果 M 的讀寫(xiě)頭向右的讀寫(xiě)頭向右移動(dòng)到帶上以前沒(méi)有讀到的位置，那么移動(dòng)到帶上以前沒(méi)有讀到的位置，那么 S 必須增加分配給這條帶的存儲(chǔ)空必須增加分配給這條帶的存儲(chǔ)空間。為此，它把自己的帶的一部分向右移動(dòng)一格。間。為此，它把自己的帶的一部分向右移動(dòng)一格。27模型間的復(fù)雜性關(guān)系01010Maaa ba #01010#aaa#ba# S模擬模擬M 的每一步，的每一步，

29、S執(zhí)行兩次掃描，執(zhí)行兩次掃描，還可能最多向右移動(dòng)還可能最多向右移動(dòng)k次。次。每一次用時(shí)每一次用時(shí)O(t(n) ，所以，模擬，所以，模擬M 的一步操作，的一步操作，S總共耗時(shí)總共耗時(shí)O(t(n) ?，F(xiàn)在，來(lái)界定模擬所需要的全部時(shí)間。在開(kāi)始階段，現(xiàn)在，來(lái)界定模擬所需要的全部時(shí)間。在開(kāi)始階段， S讓它的帶形成恰當(dāng)?shù)淖屗膸纬汕‘?dāng)?shù)母袷礁袷?，這需要這需要 O(t(n)步。隨后，步。隨后， S模擬模擬 M 的的 t(n)步操作，每模擬一步需要步操作，每模擬一步需要O(t(n) 步，所以模擬部分需要步，所以模擬部分需要 t(n) O(t(n)= O(t2(n)步。因此，整個(gè)的模步。因此，整個(gè)的模擬過(guò)程需

30、要擬過(guò)程需要O(n)+ O(t2(n)步。步。假定假定t(n) n（這是合理的假定，因?yàn)槿绻麜r(shí)間更少，（這是合理的假定，因?yàn)槿绻麜r(shí)間更少， M連輸入都讀不完）連輸入都讀不完），則，則S的運(yùn)行時(shí)間是的運(yùn)行時(shí)間是O(t2(n)，證畢。，證畢。28模型間的復(fù)雜性關(guān)系設(shè)設(shè) N 是一個(gè)非確定型圖靈機(jī)，并且是一個(gè)判定機(jī)。是一個(gè)非確定型圖靈機(jī)，并且是一個(gè)判定機(jī)。N 的運(yùn)行時(shí)間是函數(shù)的運(yùn)行時(shí)間是函數(shù) f : NN ，其中其中 f(n) 是在任何是在任何長(zhǎng)度為長(zhǎng)度為 n 的輸入上所有的計(jì)算分支中最大步數(shù)的輸入上所有的計(jì)算分支中最大步數(shù)。29模型間的復(fù)雜性關(guān)系設(shè)設(shè) t(n) 是一個(gè)函數(shù)，是一個(gè)函數(shù)， t(n)n

31、。則每一個(gè)。則每一個(gè) t(n) 時(shí)間時(shí)間的的非確定型單帶圖靈機(jī)非確定型單帶圖靈機(jī)都與某一都與某一 2O(t(n) 時(shí)間時(shí)間的確定的確定型圖靈機(jī)型圖靈機(jī)等價(jià)。等價(jià)。設(shè)設(shè)N是一個(gè)在時(shí)間是一個(gè)在時(shí)間t(n)內(nèi)運(yùn)行的非確定型內(nèi)運(yùn)行的非確定型TM ，構(gòu)造確定型，構(gòu)造確定型TM D，D通過(guò)搜索通過(guò)搜索N 的非確定型計(jì)算樹(shù)來(lái)模擬的非確定型計(jì)算樹(shù)來(lái)模擬N。 在長(zhǎng)度為在長(zhǎng)度為n的輸入上，的輸入上，N的非確定型計(jì)算樹(shù)的非確定型計(jì)算樹(shù)的的每一個(gè)分支的長(zhǎng)度最多是每一個(gè)分支的長(zhǎng)度最多是t(n) ，樹(shù)的，樹(shù)的每一個(gè)結(jié)點(diǎn)最多有每一個(gè)結(jié)點(diǎn)最多有b個(gè)子女個(gè)子女，其中，其中b是是N 的轉(zhuǎn)移函數(shù)所決定的合法選擇的最大值。因此的轉(zhuǎn)移

32、函數(shù)所決定的合法選擇的最大值。因此樹(shù)葉的總數(shù)最多是樹(shù)葉的總數(shù)最多是bt(n) 。0010Dxx#01x 12332312113 輸入帶模擬帶地址帶30模型間的復(fù)雜性關(guān)系模擬過(guò)程以寬度優(yōu)先法探查這棵樹(shù)。換句話(huà)說(shuō)，在訪(fǎng)問(wèn)深度為模擬過(guò)程以寬度優(yōu)先法探查這棵樹(shù)。換句話(huà)說(shuō)，在訪(fǎng)問(wèn)深度為d+1的結(jié)點(diǎn)之的結(jié)點(diǎn)之前，先訪(fǎng)問(wèn)所有深度為前，先訪(fǎng)問(wèn)所有深度為d 的結(jié)點(diǎn)。的結(jié)點(diǎn)。樹(shù)中結(jié)點(diǎn)的總數(shù)小于最大葉數(shù)的兩倍，因此用樹(shù)中結(jié)點(diǎn)的總數(shù)小于最大葉數(shù)的兩倍，因此用O(bt(n)作它的上界。作它的上界。從根出發(fā)下行到一個(gè)結(jié)點(diǎn)的時(shí)間是從根出發(fā)下行到一個(gè)結(jié)點(diǎn)的時(shí)間是O(t(n) 。因此，因此，D的運(yùn)行時(shí)間是的運(yùn)行時(shí)間是O(t(n

33、) bt(n) = 2O(t(n) 。TM D有三條帶。把它轉(zhuǎn)變?yōu)閱螏в腥龡l帶。把它轉(zhuǎn)變?yōu)閱螏M，最多使運(yùn)行時(shí)間乘方。這樣，單帶模，最多使運(yùn)行時(shí)間乘方。這樣，單帶模擬機(jī)的運(yùn)行時(shí)間是擬機(jī)的運(yùn)行時(shí)間是(2O(t(n)2 = 2O(2t(n) = 2O(t(n) ，定理得證。，定理得證。 0010Dxx#01x 12332312113 輸入帶模擬帶地址帶31主要內(nèi)容主要內(nèi)容7.1 度量復(fù)雜性度量復(fù)雜性大大 O 和小和小 o 記法、分析算法、模型間的復(fù)雜性關(guān)系記法、分析算法、模型間的復(fù)雜性關(guān)系7.2 P類(lèi)類(lèi)多項(xiàng)式時(shí)間、多項(xiàng)式時(shí)間、P 中的問(wèn)題舉例中的問(wèn)題舉例7.3 NP類(lèi)類(lèi)NP中的問(wèn)題舉例、中的問(wèn)題

34、舉例、P 與與 NP 問(wèn)題問(wèn)題7.4 NP完全性完全性多項(xiàng)式時(shí)間可歸約性、多項(xiàng)式時(shí)間可歸約性、NP 完全性的定義、庫(kù)克完全性的定義、庫(kù)克-列文定理列文定理7.5 幾個(gè)幾個(gè)NP完全問(wèn)題完全問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題32多項(xiàng)式時(shí)間q 定理定理7.8和定理和定理7.10顯示出一個(gè)重要的差別。一方面，問(wèn)題的時(shí)間復(fù)雜性顯示出一個(gè)重要的差別。一方面，問(wèn)題的時(shí)間復(fù)雜性在在確定型單帶和多帶圖靈機(jī)確定型單帶和多帶圖靈機(jī)上最多是平方或上最多是平方或多項(xiàng)式多項(xiàng)式的差異；另一方面，的差異；另一方面，在在確定型和非確定型圖靈機(jī)確定型和非確定型圖靈機(jī)上，問(wèn)題的時(shí)間

35、復(fù)雜性最多是上，問(wèn)題的時(shí)間復(fù)雜性最多是指數(shù)指數(shù)差異。差異。q 典型的指數(shù)時(shí)間算法來(lái)源于通過(guò)搜索解空間來(lái)求解問(wèn)題，這稱(chēng)為典型的指數(shù)時(shí)間算法來(lái)源于通過(guò)搜索解空間來(lái)求解問(wèn)題，這稱(chēng)為蠻力搜蠻力搜索（索（brute-force search）。例如，分解一個(gè)數(shù)為素?cái)?shù)因子的一種方法是。例如，分解一個(gè)數(shù)為素?cái)?shù)因子的一種方法是搜遍所有可能的因子。搜索空間的規(guī)模是指數(shù)的，所以這種搜索需要指搜遍所有可能的因子。搜索空間的規(guī)模是指數(shù)的，所以這種搜索需要指數(shù)時(shí)間。有時(shí)候，通過(guò)更深入地理解問(wèn)題，可以避免蠻力搜索，從而可數(shù)時(shí)間。有時(shí)候，通過(guò)更深入地理解問(wèn)題，可以避免蠻力搜索，從而可能會(huì)找到更實(shí)用的多項(xiàng)式時(shí)間算法。能會(huì)找到

36、更實(shí)用的多項(xiàng)式時(shí)間算法。q 所有合理的確定型計(jì)算模型都是所有合理的確定型計(jì)算模型都是多項(xiàng)式等價(jià)的（多項(xiàng)式等價(jià)的（polynomially equivalent），也就是說(shuō)，它們中任何一個(gè)模型都可以模擬另一個(gè)，而運(yùn)，也就是說(shuō)，它們中任何一個(gè)模型都可以模擬另一個(gè)，而運(yùn)行時(shí)間只增長(zhǎng)多項(xiàng)式倍。行時(shí)間只增長(zhǎng)多項(xiàng)式倍。當(dāng)稱(chēng)所有合理的確定型模型都多項(xiàng)式等價(jià)時(shí)當(dāng)稱(chēng)所有合理的確定型模型都多項(xiàng)式等價(jià)時(shí)，它足夠廣泛，它足夠廣泛，能容納那些和實(shí)際計(jì)算機(jī)運(yùn)行時(shí)間近似的模型能容納那些和實(shí)際計(jì)算機(jī)運(yùn)行時(shí)間近似的模型。例如，定。例如，定理理7.8表明確定型單帶和多帶固靈機(jī)模型是多項(xiàng)式等價(jià)的。表明確定型單帶和多帶固靈機(jī)模型是多

37、項(xiàng)式等價(jià)的。33多項(xiàng)式時(shí)間在理論中，在理論中，P類(lèi)扮演核心的角色，它的重要性在于：類(lèi)扮演核心的角色，它的重要性在于：1)對(duì)于所有與確定型單帶圖靈機(jī)多項(xiàng)式等價(jià)的計(jì)算模型來(lái)說(shuō)，對(duì)于所有與確定型單帶圖靈機(jī)多項(xiàng)式等價(jià)的計(jì)算模型來(lái)說(shuō)，P是不變的。是不變的。2)P大致對(duì)應(yīng)于在計(jì)算機(jī)上實(shí)際可解的那一類(lèi)問(wèn)題。大致對(duì)應(yīng)于在計(jì)算機(jī)上實(shí)際可解的那一類(lèi)問(wèn)題。第第1條表明，在數(shù)學(xué)上，條表明，在數(shù)學(xué)上，P是一個(gè)穩(wěn)健的類(lèi)，它不受所采用的具體計(jì)算模型是一個(gè)穩(wěn)健的類(lèi)，它不受所采用的具體計(jì)算模型的影響。的影響。第第2條表明，從實(shí)用的觀(guān)點(diǎn)看，條表明，從實(shí)用的觀(guān)點(diǎn)看，P是恰當(dāng)?shù)?。?dāng)一個(gè)問(wèn)題在是恰當(dāng)?shù)摹．?dāng)一個(gè)問(wèn)題在P中的時(shí)候，就中的時(shí)

38、候，就有辦法在時(shí)間有辦法在時(shí)間nk(k是常數(shù)是常數(shù))內(nèi)求解它。至于這么長(zhǎng)時(shí)間是否實(shí)用就依賴(lài)于內(nèi)求解它。至于這么長(zhǎng)時(shí)間是否實(shí)用就依賴(lài)于k和和實(shí)際的應(yīng)用情況。實(shí)際的應(yīng)用情況。P 是是確定型單帶圖靈機(jī)確定型單帶圖靈機(jī)在在多項(xiàng)式時(shí)間內(nèi)可判定多項(xiàng)式時(shí)間內(nèi)可判定的語(yǔ)言的語(yǔ)言類(lèi)。換言之，類(lèi)。換言之， P TIME(nk)k34P中的問(wèn)題舉例q 當(dāng)給出多項(xiàng)式時(shí)間算法時(shí)，給出的是算法的高層描述，沒(méi)有當(dāng)給出多項(xiàng)式時(shí)間算法時(shí)，給出的是算法的高層描述，沒(méi)有提及計(jì)算模型的特點(diǎn)，這樣做回避了帶和讀寫(xiě)頭運(yùn)動(dòng)的繁瑣提及計(jì)算模型的特點(diǎn)，這樣做回避了帶和讀寫(xiě)頭運(yùn)動(dòng)的繁瑣細(xì)節(jié)。細(xì)節(jié)。q 分析一個(gè)算法，證明它在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，需要

39、兩步：分析一個(gè)算法，證明它在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，需要兩步：1) 必須為算法在長(zhǎng)為必須為算法在長(zhǎng)為 n 的輸入上運(yùn)行時(shí)所需要的步驟給出多的輸入上運(yùn)行時(shí)所需要的步驟給出多項(xiàng)式上界（一般用大項(xiàng)式上界（一般用大 O 記法）。記法）。2) 必須考慮算法描述中的每一步，保證它們都可以由合理的必須考慮算法描述中的每一步，保證它們都可以由合理的確定型模型在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)。確定型模型在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)。q 需要注意的問(wèn)題所用的編碼方法。合理的方法就是允許在多需要注意的問(wèn)題所用的編碼方法。合理的方法就是允許在多項(xiàng)式時(shí)間內(nèi)把對(duì)象編碼項(xiàng)式時(shí)間內(nèi)把對(duì)象編碼/解碼為自然的內(nèi)部表示或其它合理的解碼為自然的內(nèi)部表示或其它合理

40、的編碼。編碼。q 圖的一種合理編碼是它的結(jié)點(diǎn)和邊的序列。另一種是相鄰矩圖的一種合理編碼是它的結(jié)點(diǎn)和邊的序列。另一種是相鄰矩陣，其中若從結(jié)點(diǎn)陣，其中若從結(jié)點(diǎn) i 到結(jié)點(diǎn)到結(jié)點(diǎn) j 有邊，則第有邊，則第 ( i , j ) 項(xiàng)為項(xiàng)為 1，否則，否則為為 0。35P中的問(wèn)題舉例-PATH有向圖有向圖 G 包含結(jié)點(diǎn)包含結(jié)點(diǎn) s 和和 t ，如圖所示。，如圖所示。PATH 問(wèn)題問(wèn)題就是要就是要確定是否存在從確定是否存在從 s 到到 t 的有向路徑的有向路徑。PATH = | G 是具有從是具有從 s 到到 t 的有向路徑的有向圖的有向路徑的有向圖st36P中的問(wèn)題舉例-PATHPATHP 證明思路：證明

41、思路： 通過(guò)給出判定通過(guò)給出判定PATH的多項(xiàng)式時(shí)間算法來(lái)證明該定理。的多項(xiàng)式時(shí)間算法來(lái)證明該定理。PATH 的蠻力算法的蠻力算法通過(guò)通過(guò)考察考察 G 中所有可能路徑來(lái)確定是否存在從中所有可能路徑來(lái)確定是否存在從 s 到到 t 的的有向路徑有向路徑。一條可能路徑就是一條可能路徑就是 G 中長(zhǎng)度最多為中長(zhǎng)度最多為 m 的結(jié)點(diǎn)序列，的結(jié)點(diǎn)序列， m 是是 G 中的節(jié)點(diǎn)數(shù)。中的節(jié)點(diǎn)數(shù)。但是這些可能的路徑數(shù)是但是這些可能的路徑數(shù)是 mm，這是，這是 G 中結(jié)點(diǎn)數(shù)的指數(shù)倍。因此該蠻力算中結(jié)點(diǎn)數(shù)的指數(shù)倍。因此該蠻力算法消耗指數(shù)時(shí)間。法消耗指數(shù)時(shí)間。為了獲得為了獲得 PATH 的多項(xiàng)式時(shí)間算法，必須設(shè)法避免

42、蠻力搜索。一種方法是的多項(xiàng)式時(shí)間算法，必須設(shè)法避免蠻力搜索。一種方法是采用圖搜索方法，如寬度優(yōu)先搜索。連續(xù)標(biāo)記采用圖搜索方法，如寬度優(yōu)先搜索。連續(xù)標(biāo)記 G 中從中從 s 出發(fā)，長(zhǎng)度為出發(fā)，長(zhǎng)度為 1, 2, 3 直到直到 m 的有向路徑可達(dá)的所有節(jié)點(diǎn)。的有向路徑可達(dá)的所有節(jié)點(diǎn)。用多項(xiàng)式可以容易地來(lái)界定該策略的運(yùn)行時(shí)間。用多項(xiàng)式可以容易地來(lái)界定該策略的運(yùn)行時(shí)間。37PATHPPATH 的一個(gè)多項(xiàng)式時(shí)間算法的一個(gè)多項(xiàng)式時(shí)間算法 M 運(yùn)行如下：運(yùn)行如下：M“對(duì)輸入對(duì)輸入 G, s, t，G 是包含結(jié)點(diǎn)是包含結(jié)點(diǎn) s 和和 t 的有向圖：的有向圖： 1) 在結(jié)點(diǎn)在結(jié)點(diǎn) s 上做標(biāo)記。上做標(biāo)記。 2)

43、復(fù)重下面步驟復(fù)重下面步驟 3，直到不再有結(jié)點(diǎn)被標(biāo)記。，直到不再有結(jié)點(diǎn)被標(biāo)記。 3) 掃描掃描 G 的所有邊。如果找到一條邊的所有邊。如果找到一條邊 (a, b)， a 被標(biāo)記，被標(biāo)記， 而而 b 沒(méi)有被標(biāo)記，那么標(biāo)記沒(méi)有被標(biāo)記，那么標(biāo)記 b。 4) 若若 t 被標(biāo)記，則被標(biāo)記，則接受接受；否則，；否則，拒絕拒絕?！辈襟E步驟 1 和和 4 只執(zhí)行一次只執(zhí)行一次。步驟步驟 3 最多執(zhí)行最多執(zhí)行 m 次次，因?yàn)槌詈笠淮瓮?，每一，因?yàn)槌詈笠淮瓮?，每一次?zhí)行都要標(biāo)記次執(zhí)行都要標(biāo)記 G 中的一個(gè)未標(biāo)記的結(jié)點(diǎn)。所以用到的總步數(shù)最多是中的一個(gè)未標(biāo)記的結(jié)點(diǎn)。所以用到的總步數(shù)最多是1+1+m，是，是 G 的規(guī)

44、模的多項(xiàng)式。的規(guī)模的多項(xiàng)式。 M 的步驟的步驟 1 和和 4 很容易用任問(wèn)合理的確定型模型在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)。很容易用任問(wèn)合理的確定型模型在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)。步驟步驟 3 需要掃描輸入，檢查某些結(jié)點(diǎn)是否被標(biāo)記，這也容易在多項(xiàng)式時(shí)間需要掃描輸入，檢查某些結(jié)點(diǎn)是否被標(biāo)記，這也容易在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)。所以?xún)?nèi)實(shí)現(xiàn)。所以 M 是是 PATH 的多項(xiàng)式時(shí)間算法。的多項(xiàng)式時(shí)間算法。 38P中的問(wèn)題舉例- RELPRIMERELPRIME 代表檢查兩個(gè)數(shù)是否是互素問(wèn)題。代表檢查兩個(gè)數(shù)是否是互素問(wèn)題。RELPRIME = | x 與與 y 互素互素RELPRIMEP 解決該問(wèn)題的一種算法是搜索這兩個(gè)數(shù)的所有可能

45、的公因子。如果沒(méi)有發(fā)解決該問(wèn)題的一種算法是搜索這兩個(gè)數(shù)的所有可能的公因子。如果沒(méi)有發(fā)現(xiàn)大于現(xiàn)大于 1 的公因子，就接受。然而，用二進(jìn)制或其它任何以的公因子，就接受。然而，用二進(jìn)制或其它任何以 k 為基的記法為基的記法(k2) 表示的數(shù)字的大小是它表示長(zhǎng)度的指數(shù)倍。因此該蠻力算法需要搜遍表示的數(shù)字的大小是它表示長(zhǎng)度的指數(shù)倍。因此該蠻力算法需要搜遍指數(shù)多個(gè)可能的因子，消耗指數(shù)的運(yùn)行時(shí)間。指數(shù)多個(gè)可能的因子，消耗指數(shù)的運(yùn)行時(shí)間。改用一種古老的數(shù)值計(jì)算過(guò)程來(lái)求解該問(wèn)題，稱(chēng)為改用一種古老的數(shù)值計(jì)算過(guò)程來(lái)求解該問(wèn)題，稱(chēng)為歐幾里德算法歐幾里德算法(Euclidean algorithm)，來(lái)計(jì)算最大公因子。

46、兩個(gè)自然數(shù)的，來(lái)計(jì)算最大公因子。兩個(gè)自然數(shù)的最大公因子最大公因子(greatest common divisor)，即為，即為gcd(x, y)，能同時(shí)整除，能同時(shí)整除 x 和和 y 的最大整數(shù)。的最大整數(shù)。39RELPRIMEP 證明證明: 歐幾里德算法歐幾里德算法 E 如下：如下：E=“對(duì)輸入對(duì)輸入，x 和和 y 是二進(jìn)制表示的自然數(shù)：是二進(jìn)制表示的自然數(shù)：1) 重復(fù)下面的操作，直到重復(fù)下面的操作，直到 y=0.2) 賦值賦值 x x mod y3) 交換交換 x 和和 y4) 輸出輸出 x?！憋@然，若顯然，若 E 在多項(xiàng)式時(shí)間內(nèi)運(yùn)行且正確，則在多項(xiàng)式時(shí)間內(nèi)運(yùn)行且正確，則 R 也在多項(xiàng)式時(shí)

47、間內(nèi)運(yùn)行且正也在多項(xiàng)式時(shí)間內(nèi)運(yùn)行且正確。所以只需分析確。所以只需分析 E 的時(shí)間和正確性。的時(shí)間和正確性。步驟步驟2的每一次執(zhí)行的每一次執(zhí)行(除了第一次有可能例外除了第一次有可能例外)，都把，都把 x 的值至少減少一半。的值至少減少一半。 每一次執(zhí)行步驟每一次執(zhí)行步驟 3都使都使 x 和和 y 的值相互交換，所以每?jī)纱窝h(huán)就使得的值相互交換，所以每?jī)纱窝h(huán)就使得 x 和和 y原先的值至少減少一半。于是步驟原先的值至少減少一半。于是步驟 2 和和 3 執(zhí)行的最大次數(shù)是執(zhí)行的最大次數(shù)是 2log2x 和和 2log2y 中較小的那一個(gè)。這兩個(gè)對(duì)數(shù)與表示的長(zhǎng)度成正比，步驟的執(zhí)行次數(shù)中較小的那一個(gè)。這

48、兩個(gè)對(duì)數(shù)與表示的長(zhǎng)度成正比，步驟的執(zhí)行次數(shù)是是 O(n)。 E 的每一步僅消耗多項(xiàng)式時(shí)間，所以整個(gè)運(yùn)行時(shí)間是多項(xiàng)式的。的每一步僅消耗多項(xiàng)式時(shí)間，所以整個(gè)運(yùn)行時(shí)間是多項(xiàng)式的。算法算法 R 以以 E 為子程序求解為子程序求解 RELPRIMER=“對(duì)輸入對(duì)輸入 ，x 和和 y 是二進(jìn)制表示的自然數(shù)：是二進(jìn)制表示的自然數(shù)： 1) 在在 上運(yùn)行上運(yùn)行E。 2) 若結(jié)果為若結(jié)果為 1，就，就接受接受；否則；否則拒絕拒絕?！?0P中的問(wèn)題舉例-上下文無(wú)關(guān)語(yǔ)言每一個(gè)上下文無(wú)關(guān)語(yǔ)言都是每一個(gè)上下文無(wú)關(guān)語(yǔ)言都是 P 的成員。的成員。證明思路：證明思路： 定理定理4.8 證明了每一個(gè)證明了每一個(gè) CFL 是可判定

49、的，并且為每一個(gè)是可判定的，并且為每一個(gè) CFL給出了判定算法。如果那個(gè)算法在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，那么本定理作為推給出了判定算法。如果那個(gè)算法在多項(xiàng)式時(shí)間內(nèi)運(yùn)行，那么本定理作為推論就必然成立?；貞浤莻€(gè)算法，看它運(yùn)行得是否夠快。論就必然成立?；貞浤莻€(gè)算法，看它運(yùn)行得是否夠快。 令令 L 是一個(gè)由是一個(gè)由 CFG G 產(chǎn)生的產(chǎn)生的 CFG，G 是喬姆斯基范式。由問(wèn)題是喬姆斯基范式。由問(wèn)題2.26知：因知：因 G 是喬姆斯基范式，是喬姆斯基范式，任何得到字符串任何得到字符串 w 的推導(dǎo)都有的推導(dǎo)都有 2n-1步步，n 是是 w 的長(zhǎng)度。當(dāng)給的長(zhǎng)度。當(dāng)給 L 的判定機(jī)輸入長(zhǎng)為的判定機(jī)輸入長(zhǎng)為 n 的字符

50、串時(shí)，它的字符串時(shí)，它通過(guò)試遍所有可能的通過(guò)試遍所有可能的 2n-1 步推導(dǎo)來(lái)判定步推導(dǎo)來(lái)判定 L。如果其中有一個(gè)得到。如果其中有一個(gè)得到 w 的推導(dǎo)，該判定機(jī)就接受；的推導(dǎo)，該判定機(jī)就接受；否則，就拒絕。否則，就拒絕。 分析一下該算法可知，它不能在多項(xiàng)式時(shí)間內(nèi)運(yùn)行。分析一下該算法可知，它不能在多項(xiàng)式時(shí)間內(nèi)運(yùn)行。 k 步推導(dǎo)的數(shù)量步推導(dǎo)的數(shù)量可能達(dá)到可能達(dá)到 k 的指數(shù)，所以該算法可能需要指數(shù)時(shí)間。的指數(shù)，所以該算法可能需要指數(shù)時(shí)間。41P中的問(wèn)題舉例-上下文無(wú)關(guān)語(yǔ)言為了獲得多項(xiàng)式時(shí)間算法，在此介紹一種強(qiáng)有力的技術(shù)，稱(chēng)為為了獲得多項(xiàng)式時(shí)間算法，在此介紹一種強(qiáng)有力的技術(shù)，稱(chēng)為動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。這

51、種技術(shù)通過(guò)累積小的子問(wèn)題的信息來(lái)解決大的問(wèn)題。把子問(wèn)題的解都記這種技術(shù)通過(guò)累積小的子問(wèn)題的信息來(lái)解決大的問(wèn)題。把子問(wèn)題的解都記錄下來(lái)，這樣就只需對(duì)它求解一次。為此，把所有了問(wèn)題編成一張表，當(dāng)錄下來(lái)，這樣就只需對(duì)它求解一次。為此，把所有了問(wèn)題編成一張表，當(dāng)碰到它們時(shí)，把它們的解系統(tǒng)地填入表格。碰到它們時(shí)，把它們的解系統(tǒng)地填入表格。在本例中，考慮在本例中，考慮 G 的每一個(gè)變?cè)欠癞a(chǎn)生的每一個(gè)變?cè)欠癞a(chǎn)生 w 的每一個(gè)子串這樣的子問(wèn)題的每一個(gè)子串這樣的子問(wèn)題。算法把子問(wèn)題的解填入一張。算法把子問(wèn)題的解填入一張 nn表格。對(duì)于表格。對(duì)于 ij，表的第，表的第 (i, j) 項(xiàng)包含產(chǎn)項(xiàng)包含產(chǎn)生子串生子

52、串 wi wi+1 wj 的所有變?cè)?。的所有變?cè)?ij 的表項(xiàng)沒(méi)有使用。的表項(xiàng)沒(méi)有使用。算法為算法為 w 的每一子串填寫(xiě)表項(xiàng)。首先為長(zhǎng)為的每一子串填寫(xiě)表項(xiàng)。首先為長(zhǎng)為 1 的子串填寫(xiě)表項(xiàng)，然后是長(zhǎng)的子串填寫(xiě)表項(xiàng)，然后是長(zhǎng)為為 2 的子串，依此類(lèi)推。它利用短子串的表頂內(nèi)容來(lái)輔助確定長(zhǎng)子串的表的子串，依此類(lèi)推。它利用短子串的表頂內(nèi)容來(lái)輔助確定長(zhǎng)子串的表項(xiàng)內(nèi)容。項(xiàng)內(nèi)容。42P中的問(wèn)題舉例-上下文無(wú)關(guān)語(yǔ)言 例如，假定該算法已經(jīng)確定了由哪些變?cè)a(chǎn)生所有長(zhǎng)度不超過(guò)例如，假定該算法已經(jīng)確定了由哪些變?cè)a(chǎn)生所有長(zhǎng)度不超過(guò) k 的的子串。為了確定變?cè)哟?。為了確定變?cè)?A 是否產(chǎn)生某一長(zhǎng)為是否產(chǎn)生某一長(zhǎng)為 k

53、+1 的子串，算法把該子串以的子串，算法把該子串以k種可能方式分裂為非空的兩段。對(duì)于每一種分裂方式，算法考察每一條種可能方式分裂為非空的兩段。對(duì)于每一種分裂方式，算法考察每一條規(guī)則規(guī)則 A BC ，利用以前計(jì)算的表項(xiàng)來(lái)確定是否，利用以前計(jì)算的表項(xiàng)來(lái)確定是否 B 產(chǎn)生第一段而且產(chǎn)生第一段而且 C 產(chǎn)產(chǎn)生第二段。如果生第二段。如果 B 和和 C 都產(chǎn)生各自的段，那么都產(chǎn)生各自的段，那么 A 就產(chǎn)生該子串，并且被就產(chǎn)生該子串，并且被加入相關(guān)聯(lián)的表項(xiàng)。算法從長(zhǎng)為加入相關(guān)聯(lián)的表項(xiàng)。算法從長(zhǎng)為 1 的串開(kāi)始，對(duì)規(guī)則的串開(kāi)始，對(duì)規(guī)則 A b 考察表格?？疾毂砀瘛?43P中的問(wèn)題舉例-上下文無(wú)關(guān)語(yǔ)言證明：證明

54、：令令G 是產(chǎn)生是產(chǎn)生CFL L的喬姆斯基范式的的喬姆斯基范式的CFG，假設(shè)，假設(shè)S是起始變?cè)?。是起始變?cè)?D=“對(duì)輸入對(duì)輸入w =w1wn:1）若）若w = 且且S 是一條規(guī)則，則是一條規(guī)則，則接受接受。 處理處理w = 的情況的情況2）For i = 1 to n： 考察每一長(zhǎng)為考察每一長(zhǎng)為1的子串的子串3） 對(duì)每一個(gè)變?cè)獙?duì)每一個(gè)變?cè)?A：4） 檢查檢查A b是否是一條規(guī)則，其中是否是一條規(guī)則，其中b = wi。5） 若是，把若是，把A放入放入table（i，i）。）。6）For l = 2 to n l是子串長(zhǎng)度是子串長(zhǎng)度7） For I = 1 to n-l+1 i是子串的起始位置是

55、子串的起始位置8） 令令j = i +l-1 j是子串的起始位置是子串的起始位置9） For k =i to j-1 k是分裂位置是分裂位置10） 對(duì)每一條規(guī)則對(duì)每一條規(guī)則 A BC：12） 若若table（i，k）包含）包含B且且table（k+1，j）包含）包含C，則把，則把 A 放入放入table（i，j）12）若）若S在在table（1，n）中，則）中，則接受接受；否則；否則拒絕拒絕?！?4P中的問(wèn)題舉例-上下文無(wú)關(guān)語(yǔ)言 現(xiàn)在分析現(xiàn)在分析D。每一步很容易在多項(xiàng)式時(shí)間內(nèi)運(yùn)行。步驟。每一步很容易在多項(xiàng)式時(shí)間內(nèi)運(yùn)行。步驟4和和5最多運(yùn)行最多運(yùn)行nv次，其中次，其中v是是G中的變?cè)獢?shù)，是與中的

56、變?cè)獢?shù)，是與n無(wú)關(guān)的固定常數(shù)；因此這兩步運(yùn)行無(wú)關(guān)的固定常數(shù)；因此這兩步運(yùn)行O(n)次。步驟次。步驟6最多運(yùn)行最多運(yùn)行n 次。步驟次。步驟6每運(yùn)行一次，步驟每運(yùn)行一次，步驟7最多運(yùn)行最多運(yùn)行n次。步次。步驟驟7每運(yùn)行一次，步驟每運(yùn)行一次，步驟8和和9最多運(yùn)行最多運(yùn)行n次。步驟次。步驟9每運(yùn)行一次，步驟每運(yùn)行一次，步驟10運(yùn)行運(yùn)行r 次，這里次，這里r是是G的規(guī)則數(shù)，是另一個(gè)固定常數(shù)。所以步驟的規(guī)則數(shù)，是另一個(gè)固定常數(shù)。所以步驟11，即該算法的內(nèi)，即該算法的內(nèi)層循環(huán)，運(yùn)行層循環(huán)，運(yùn)行O(n3)次?？傆?jì)次?？傆?jì)D執(zhí)行執(zhí)行O(n3)步。步。45主要內(nèi)容主要內(nèi)容7.1 度量復(fù)雜性度量復(fù)雜性大大 O 和小

57、和小 o 記法、分析算法、模型間的復(fù)雜性關(guān)系記法、分析算法、模型間的復(fù)雜性關(guān)系7.2 P類(lèi)類(lèi)多項(xiàng)式時(shí)間、多項(xiàng)式時(shí)間、P 中的問(wèn)題舉例中的問(wèn)題舉例7.3 NP類(lèi)類(lèi)NP中的問(wèn)題舉例、中的問(wèn)題舉例、P 與與 NP 問(wèn)題問(wèn)題7.4 NP完全性完全性多項(xiàng)式時(shí)間可歸約性、多項(xiàng)式時(shí)間可歸約性、NP 完全性的定義、庫(kù)克完全性的定義、庫(kù)克-列文定理列文定理7.5 幾個(gè)幾個(gè)NP完全問(wèn)題完全問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題頂點(diǎn)覆蓋問(wèn)題、哈密頓路徑問(wèn)題、子集和問(wèn)題46NP 類(lèi)q 許多問(wèn)題可以避免使用蠻力搜索而獲得多項(xiàng)式時(shí)間解法。許多問(wèn)題可以避免使用蠻力搜索而獲得多項(xiàng)式時(shí)間解法。但是，在某些其它問(wèn)題中，包括

58、許多有趣而有用的問(wèn)題，但是，在某些其它問(wèn)題中，包括許多有趣而有用的問(wèn)題，避免蠻力搜索的努力還沒(méi)有成功，求解它們的多項(xiàng)式時(shí)間避免蠻力搜索的努力還沒(méi)有成功，求解它們的多項(xiàng)式時(shí)間算法還沒(méi)有找到。算法還沒(méi)有找到。q 可能這些問(wèn)題具有未知原理的多項(xiàng)式時(shí)間算法，但至今還可能這些問(wèn)題具有未知原理的多項(xiàng)式時(shí)間算法，但至今還沒(méi)有被發(fā)現(xiàn)，或者它們中的某些問(wèn)題就是不能在多項(xiàng)式時(shí)沒(méi)有被發(fā)現(xiàn)，或者它們中的某些問(wèn)題就是不能在多項(xiàng)式時(shí)間內(nèi)解決，它們可能是間內(nèi)解決，它們可能是固有地難計(jì)算固有地難計(jì)算的。的。q 一個(gè)不尋常的發(fā)現(xiàn)是，一個(gè)不尋常的發(fā)現(xiàn)是，許多問(wèn)題的復(fù)雜性是聯(lián)系在一起的許多問(wèn)題的復(fù)雜性是聯(lián)系在一起的。發(fā)現(xiàn)其中一個(gè)問(wèn)

59、題的多項(xiàng)式時(shí)間算法可以用來(lái)解決整個(gè)一發(fā)現(xiàn)其中一個(gè)問(wèn)題的多項(xiàng)式時(shí)間算法可以用來(lái)解決整個(gè)一類(lèi)問(wèn)題類(lèi)問(wèn)題。47多項(xiàng)式可驗(yàn)證性q 許多事情許多事情, 猜出困難，驗(yàn)證易。猜出困難，驗(yàn)證易。q 例如，解方程例如，解方程 x10+2x+7=1035q 解方程難，解方程難，驗(yàn)算驗(yàn)算根根x=2容易容易。q HAMPATH = G,s,t | G 是包含從是包含從 s 到到 t 的哈密頓路徑的有向圖的哈密頓路徑的有向圖容易獲得指數(shù)時(shí)間算法，但不知是否能在多項(xiàng)式時(shí)間內(nèi)求解。容易獲得指數(shù)時(shí)間算法，但不知是否能在多項(xiàng)式時(shí)間內(nèi)求解。該問(wèn)題有一個(gè)特點(diǎn)，稱(chēng)為該問(wèn)題有一個(gè)特點(diǎn)，稱(chēng)為多項(xiàng)式可驗(yàn)證性多項(xiàng)式可驗(yàn)證性。雖然還不知道一種

60、雖然還不知道一種快速（即多項(xiàng)式時(shí)間）快速（即多項(xiàng)式時(shí)間）的方法來(lái)確定圖中是否包含哈的方法來(lái)確定圖中是否包含哈密頓路徑，但是如果密頓路徑，但是如果以某種方式（可能是指數(shù)時(shí)間算法）以某種方式（可能是指數(shù)時(shí)間算法）找到這樣的路找到這樣的路徑，就可以相信它的存在。即：徑，就可以相信它的存在。即：驗(yàn)證驗(yàn)證哈密頓路徑的存在可能哈密頓路徑的存在可能比確定比確定它的它的存在性存在性容易容易得多。得多。q COMPOSITES = x | x = pq，整數(shù)，整數(shù) p,q1雖然不知道判斷該問(wèn)題的多項(xiàng)式時(shí)間算法，但是容易驗(yàn)證一個(gè)數(shù)是不是雖然不知道判斷該問(wèn)題的多項(xiàng)式時(shí)間算法，但是容易驗(yàn)證一個(gè)數(shù)是不是合數(shù)合數(shù)-只需要