計算理論導引__時間復雜性

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

2、264-1) / 1000=5.846 億年億年2引言q 復雜度和時間復雜度和時間 ：每秒作：每秒作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秒秒117.9分分12.7天天35.7年年366世紀世紀3N

3、0.059秒秒58分分6.5年年3855世世紀紀2億世紀億世紀1.3*1013世紀世紀3引言Complexity：Hamilton回路問題（回路問題（HC）：任給一個無向圖）：任給一個無向圖G，問，問G中有中有Hamilton回路嗎？回路嗎？Hamilton回路是指經(jīng)過每一個頂點且每一個頂點只經(jīng)過一次的回路?；芈肥侵附?jīng)過每一個頂點且每一個頂點只經(jīng)過一次的回路。q 設設G有有n個頂點，由于回路沒有始點和終點，可以任意定一個頂點作為排列的個頂點，由于回路沒有始點和終點，可以任意定一個頂點作為排列的第一個頂點，共有（第一個頂點，共有（n-1）！個排列。當）！個排列。當n=25時，時，24！=6.2*

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

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

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

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

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

9、。9漸進分析q 因為算法的精確運行時間通常是一個復雜的表達式，所以因為算法的精確運行時間通常是一個復雜的表達式，所以一般是估計它的趨勢和級別。一般是估計它的趨勢和級別。q 通過一種稱為通過一種稱為漸進分析漸進分析 (asymptotic analysis) 的方便的估計的方便的估計形式，可以試圖了解算法在長輸入上的運行時間。形式，可以試圖了解算法在長輸入上的運行時間。q 只考慮算法運行時間的表達式的最高項，而忽略該項的系只考慮算法運行時間的表達式的最高項，而忽略該項的系數(shù)和其它低次項，因為在在長輸入上，數(shù)和其它低次項，因為在在長輸入上，最高次項最高次項的影響相的影響相比其它項比其它項占據(jù)主導地

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

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

12、不論給 c 和和 n0 賦什么值，始終不滿足賦什么值，始終不滿足定義的要求。定義的要求。12大 O 和小 o 記法例例7.4 大大O記法以一種特別的方式與對數(shù)相互記法以一種特別的方式與對數(shù)相互影響。影響。通常通常寫對數(shù)時必須寫對數(shù)時必須指明基數(shù)指明基數(shù)(或稱為對數(shù)的底或稱為對數(shù)的底)，如，如 x=log2n 。這里基數(shù)這里基數(shù) 2 表明表明該等式等價該等式等價于等式于等式 2x=n。logbn 的的值值隨著基數(shù)隨著基數(shù) b 的的改變而乘以相應的常數(shù)倍，因為改變而乘以相應的常數(shù)倍，因為有恒等式有恒等式 logbn = log2n / log2b。所以，寫。所以，寫 f(n) = O(logn)

13、時時不必再指明基數(shù)，因為不必再指明基數(shù)，因為最終最終要忽略常數(shù)因子。要忽略常數(shù)因子。13大 O 和小 o 記法q 令令 f2(n) 是函數(shù)是函數(shù) 3nlog2n+5nlog2log2n+2。 此時此時 f2(n) =O(nlogn)，因為，因為 logn 比比 log logn更占支配位置。更占支配位置。q f(n) =O(n2)+ O(n) 等價于等價于 f(n) =O(n2)q 當當 O 出現(xiàn)在指數(shù)位置，如出現(xiàn)在指數(shù)位置，如 f(n) =2O(n)，代表著，代表著 2cn 的一個上的一個上界。界。q f(n) =2O(logn)，代表，代表 nc。（由。（由 n = 2log n 得得 n

14、c = 2c log 2n）q 2O(1) 代表了同樣的界，因為表達式代表了同樣的界，因為表達式 O(1) 代表不超過某個固代表不超過某個固定常數(shù)的上界。定常數(shù)的上界。14大O 和小o 記法q 我們經(jīng)常導出我們經(jīng)常導出 nc 的界，的界，c 是大于是大于 0 的常數(shù)。這種界稱為的常數(shù)。這種界稱為多多項式界項式界 (polynamial bound)。形如。形如 的界，當?shù)慕?，?是大于是大于 0的實數(shù)時，稱為的實數(shù)時，稱為指數(shù)界指數(shù)界(exponential bound)。q 大大 O 記法記法指一個函數(shù)漸近地指一個函數(shù)漸近地不大于不大于另一個函數(shù)。另一個函數(shù)。q 小小 o 記法記法是漸進的是

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

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

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

18、n)步步。因為每一次掃描刪除兩個符號，所以。因為每一次掃描刪除兩個符號，所以最多掃描最多掃描n/2次次。于是步驟。于是步驟2和和3需要的全部時間是需要的全部時間是(n/2)O(n)=O(n2)步。步。q 在步驟在步驟4中，機器掃描一次來決定是接受還是拒絕。最多需要中，機器掃描一次來決定是接受還是拒絕。最多需要O(n)步。步。q 所以，所以，M1在長度為在長度為n的輸入上總共耗時為的輸入上總共耗時為O(n)+O(n2)+O(n)，或，或O(n2)。換。換言之，它的言之，它的運行時間是運行時間是O(n2)。18時間復雜性類令令 t : N R+ 是一個函數(shù)。定義是一個函數(shù)。定義時間復雜性類時間復雜

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

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

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

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

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

24、好的運行時間，因為光是讀輸入就需要n步。步。21A 的 C 程序A = 0k1k | k=0,1,2, . 先用用C語言寫程序判斷串 s 是否 0k1k Bool M(char *s) int L=strlen(s) /掃描一遍 O(n) if (L%2)!=0 return false; /長度不是偶數(shù) else N=L/2; for( k=1;kN; k+) / if (sk !=0) return false; /O(n) if (sk+N!=1) return false; /相當于第二條帶 O(n) return true; 判斷一個串，用 O(n)時間. 使用的資源:隨機存取,數(shù)組

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

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

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

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

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

30、過程需要O(n)+ O(t2(n)步。步。假定假定t(n) n（這是合理的假定，因為如果時間更少，（這是合理的假定，因為如果時間更少， M連輸入都讀不完）連輸入都讀不完），則，則S的運行時間是的運行時間是O(t2(n)，證畢。，證畢。27模型間的復雜性關系設設 N 是一個非確定型圖靈機，并且是一個判定機。是一個非確定型圖靈機，并且是一個判定機。N 的運行時間是函數(shù)的運行時間是函數(shù) f : NN ，其中其中 f(n) 是在任何是在任何長度為長度為 n 的輸入上所有的計算分支中最大步數(shù)的輸入上所有的計算分支中最大步數(shù)。28模型間的復雜性關系設設 t(n) 是一個函數(shù)，是一個函數(shù)， t(n)n 。則

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

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

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

34、、P 與與 NP 問題問題7.4 NP完全性完全性多項式時間可歸約性、多項式時間可歸約性、NP 完全性的定義、庫克完全性的定義、庫克-列文定理列文定理7.5 幾個幾個NP完全問題完全問題頂點覆蓋問題、哈密頓路徑問題、子集和問題頂點覆蓋問題、哈密頓路徑問題、子集和問題31多項式時間q 定理定理7.8和定理和定理7.10顯示出一個重要的差別。一方面，問題的時間復雜性顯示出一個重要的差別。一方面，問題的時間復雜性在在確定型單帶和多帶圖靈機確定型單帶和多帶圖靈機上最多是平方或上最多是平方或多項式多項式的差異；另一方面，的差異；另一方面，在在確定型和非確定型圖靈機確定型和非確定型圖靈機上，問題的時間復雜

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

36、用的多項式時間算法。q 所有合理的確定型計算模型都是所有合理的確定型計算模型都是多項式等價的（多項式等價的（polynomially equivalent），也就是說，它們中任何一個模型都可以模擬另一個，而運，也就是說，它們中任何一個模型都可以模擬另一個，而運行時間只增長多項式倍。行時間只增長多項式倍。當稱所有合理的確定型模型都多項式等價時當稱所有合理的確定型模型都多項式等價時，它足夠廣泛，它足夠廣泛，能容納那些和實際計算機運行時間近似的模型能容納那些和實際計算機運行時間近似的模型。例如，定。例如，定理理7.8表明確定型單帶和多帶固靈機模型是多項式等價的。表明確定型單帶和多帶固靈機模型是多項式

37、等價的。32多項式時間在理論中，在理論中，P類扮演核心的角色，它的重要性在于：類扮演核心的角色，它的重要性在于：1)對于所有與確定型單帶圖靈機多項式等價的計算模型來說，對于所有與確定型單帶圖靈機多項式等價的計算模型來說，P是不變的。是不變的。2)P大致對應于在計算機上實際可解的那一類問題。大致對應于在計算機上實際可解的那一類問題。第第1條表明，在數(shù)學上，條表明，在數(shù)學上，P是一個穩(wěn)健的類，它不受所采用的具體計算模型是一個穩(wěn)健的類，它不受所采用的具體計算模型的影響。的影響。第第2條表明，從實用的觀點看，條表明，從實用的觀點看，P是恰當?shù)?。當一個問題在是恰當?shù)?。當一個問題在P中的時候，就中的時候，

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

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

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

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

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

43、下面步驟復重下面步驟 3，直到不再有結(jié)點被標記。，直到不再有結(jié)點被標記。 3) 掃描掃描 G 的所有邊。如果找到一條邊的所有邊。如果找到一條邊 (a, b)， a 被標記，被標記， 而而 b 沒有被標記，那么標記沒有被標記，那么標記 b。 4) 若若 t 被標記，則被標記，則接受接受；否則，；否則，拒絕拒絕?！辈襟E步驟 1 和和 4 只執(zhí)行一次只執(zhí)行一次。步驟步驟 3 最多執(zhí)行最多執(zhí)行 m 次次，因為除最后一次外，每一，因為除最后一次外，每一次執(zhí)行都要標記次執(zhí)行都要標記 G 中的一個未標記的結(jié)點。所以用到的總步數(shù)最多是中的一個未標記的結(jié)點。所以用到的總步數(shù)最多是1+1+m，是，是 G 的規(guī)模的

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

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

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

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

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

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

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

51、術通過累積小的子問題的信息來解決大的問題。把子問題的解都記這種技術通過累積小的子問題的信息來解決大的問題。把子問題的解都記錄下來，這樣就只需對它求解一次。為此，把所有了問題編成一張表，當錄下來，這樣就只需對它求解一次。為此，把所有了問題編成一張表，當碰到它們時，把它們的解系統(tǒng)地填入表格。碰到它們時，把它們的解系統(tǒng)地填入表格。在本例中，考慮在本例中，考慮 G 的每一個變元是否產(chǎn)生的每一個變元是否產(chǎn)生 w 的每一個子串這樣的子問題的每一個子串這樣的子問題。算法把子問題的解填入一張。算法把子問題的解填入一張 nn表格。對于表格。對于 ij，表的第，表的第 (i, j) 項包含產(chǎn)項包含產(chǎn)生子串生子串

52、wi wi+1 wj 的所有變元。的所有變元。 ij 的表項沒有使用。的表項沒有使用。算法為算法為 w 的每一子串填寫表項。首先為長為的每一子串填寫表項。首先為長為 1 的子串填寫表項，然后是長的子串填寫表項，然后是長為為 2 的子串，依此類推。它利用短子串的表頂內(nèi)容來輔助確定長子串的表的子串，依此類推。它利用短子串的表頂內(nèi)容來輔助確定長子串的表項內(nèi)容。項內(nèi)容。41P中的問題舉例-上下文無關語言 例如，假定該算法已經(jīng)確定了由哪些變元產(chǎn)生所有長度不超過例如，假定該算法已經(jīng)確定了由哪些變元產(chǎn)生所有長度不超過 k 的的子串。為了確定變元子串。為了確定變元 A 是否產(chǎn)生某一長為是否產(chǎn)生某一長為 k+1

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

54、令G 是產(chǎn)生是產(chǎn)生CFL L的喬姆斯基范式的的喬姆斯基范式的CFG，假設，假設S是起始變元。是起始變元。 D=“對輸入對輸入w =w1wn:1）若）若w = 且且S 是一條規(guī)則，則是一條規(guī)則，則接受接受。 處理處理w = 的情況的情況2）For i = 1 to n： 考察每一長為考察每一長為1的子串的子串3） 對每一個變元對每一個變元 A：4） 檢查檢查A b是否是一條規(guī)則，其中是否是一條規(guī)則，其中b = wi。5） 若是，把若是，把A放入放入table（i，i）。）。6）For l = 2 to n l是子串長度是子串長度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） 對每一條規(guī)則對每一條規(guī)則 A BC：12） 若若table（i，k）包含）包含B且且table（k+1，j）包含）包含C，則把，則把 A 放入放入table（i，j）12）若）若S在在table（1，n）中，則）中，則接受接受；否則；否則拒絕拒絕?！?3P中的問題舉例-上下文無關語言 現(xiàn)在分析現(xiàn)在分析D。每一步很容易在多項式時間內(nèi)運行。步驟。每一步很容易在多項式時間內(nèi)運行。步驟4和和5最多運行最多運行nv次，其中次，其中v是是G中的變元數(shù)，是與中的變元

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

57、 o 記法、分析算法、模型間的復雜性關系記法、分析算法、模型間的復雜性關系7.2 P類類多項式時間、多項式時間、P 中的問題舉例中的問題舉例7.3 NP類類NP中的問題舉例、中的問題舉例、P 與與 NP 問題問題7.4 NP完全性完全性多項式時間可歸約性、多項式時間可歸約性、NP 完全性的定義、庫克完全性的定義、庫克-列文定理列文定理7.5 幾個幾個NP完全問題完全問題頂點覆蓋問題、哈密頓路徑問題、子集和問題頂點覆蓋問題、哈密頓路徑問題、子集和問題45NP 類q 許多問題可以避免使用蠻力搜索而獲得多項式時間解法。許多問題可以避免使用蠻力搜索而獲得多項式時間解法。但是，在某些其它問題中，包括許多

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

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

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