測度和復(fù)雜性分類

《測度和復(fù)雜性分類》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、語言與計算理論導(dǎo)引可計算函數(shù)第五部分計算復(fù)雜性導(dǎo)引到現(xiàn)在，在我們討論決策問題時，我們只考慮問題是否具有可解的性質(zhì)。在現(xiàn)實生活中，用于解決問題的計算資源是有限的：可獲得的時間和空間都是有限的。結(jié)果，一些可解的問題的中等規(guī)模的實例在實際中都變得很難以解決。在第5部分，我們考慮鑒別難解問題的方法，主要通過描述解決問題的一定規(guī)模的實例時，所需要的時間和內(nèi)存的數(shù)量。雖然，強調(diào)的重點是運行時間，我們也給出有關(guān)空間的基本定義，并提到涉及空間的最基本的結(jié)果。在第14章，我們首先引入涉及增長率的記號和術(shù)語，這允許我們在后面章節(jié)以合理的方式討論象“多少時間？”這樣的問題。我們把這些數(shù)量問題與我們特

2、定的計算模型相聯(lián)系，然后討論一些基本的復(fù)雜類。這也是根據(jù)問題和語言內(nèi)在的復(fù)雜性對它們分類的方法。為了區(qū)分易解問題和難解問題（注意，前面我們討論的可解問題和無解問題），正如我們將在第15章討論的，常用的標準是在圖林機上是多項式時間可解的。根據(jù)這個標準，許多問題是易解的，也有些問題是難解的。我們可以修改第12章的規(guī)約技術(shù)得到這兩類問題的例子。也許更有趣的問題是根據(jù)這個標準，至今仍然無法判斷的一些問題，沒有人發(fā)現(xiàn)這些問題的多項式時間解決方法，但是也沒有人能夠證明不存在多項式時間解決方法。NP完全的概念就是接近這個主題的一個方法。在第15章的最后兩節(jié)，我們給出可滿足問題的NP完全性的c

3、ook證明和一些通過多項式時間規(guī)約被證明是NP完全的組合問題的例子。14測度和復(fù)雜性分類14.1函數(shù)的增長率計算問題的復(fù)雜性能夠通過固定的計算模型來討論，主要考慮為了解決這個問題，需要多少機器的資源（通常指時間和空間）。為了對兩個問題內(nèi)在復(fù)雜性進行有意義的比較，有必要考察一定范圍內(nèi)的實例的解決情況。如果我們把運行時間作為標準，比如，最常用的方法是比較兩個運行時間的增長率，每個運行時間都看成是實例規(guī)模的函數(shù)。我們引入一些處理運行時間的數(shù)量的增長率的定義和記號。我們從一個比較4個簡單函數(shù)的例子開始。例子14.1我們考慮函數(shù)p1(n)=2n2p2(n)=n2+3n+7P3(n)=n3

4、q(n)=2n表14.1顯示了這4個函數(shù)對應(yīng)部分變量取值n的各自的函數(shù)值，這些函數(shù)值很清楚顯示了每個函數(shù)的增長趨勢。對于比較小的值n，p2(n)的值遠遠大于p1(n)，但是當n=1000時，p2(n)中低階的項3n+7變得相對可忽略了，而p1中的因子2幾乎完全決定了p1和p2之間的差別。p3是更高階的多項式，盡管沒有額外的因子和低階項，但是它的值的增長速度比前兩個函數(shù)都要快很多。更驚人的增長趨勢體現(xiàn)在第4個指數(shù)函數(shù)q上。我們再次看到對于最前面的幾個小數(shù)值沒有什么特別的地方，但是對于n=10之后的數(shù)值，它就比其他3個函數(shù)值都要大了，當n=1000時，p3(n)是1百萬，而q(n)

5、則是難以想象地大了。如果表中數(shù)據(jù)的單位是納秒（nanosecond，又譯毫微秒，一秒的10億分之一），那么p3(1000)表示1秒，而q(1000)表示超過3*10282世紀。加入表14.113陶曉鵬Copyright2003語言與計算理論導(dǎo)引可計算函數(shù)表14.1展示了不同增長率的效果，p1和p2有不同的規(guī)模，主要是因為p1的因子2，但是它們的增長率是一致的。立方多項式的增長率更大一些，但是這三個多項式的增長率都遠遠小于指數(shù)函數(shù)。一旦我們有了能夠精確描述增長率的定義，其中一個我們感興趣的主要區(qū)別將是多項式增長率和指數(shù)增長率之間的區(qū)別。這個例子顯示的許多明顯的特征將體現(xiàn)在定義中。

6、定義14.1如果f,g:N?N是部分函數(shù)，每個函數(shù)除了在有限個點外，其他值都是有定義的。如果存在常量C和n0，使得對于每個n>=n0，f(n)和g(n)都是有定義的，且f(n)<=Cg(n)，那么我們寫f(n)=O(g(n))（或者簡單地，f=O(g)）如果對于每個正常數(shù)C，存在一個常量n0，使得對于每個n>=n0，都有f(n)<=Cg(n)，那么我們寫f(n)=o(g(n))（或者簡單地，f=o(g)）最后，如果f=O(g)且g=O(f)，則寫成f=Q(g)語句f=O(g)，f=o(g)和f=Q(g)分別讀著“f是g的大O”，“f是g的小o”和“f是g的大Q”。所有這些語句可

7、以用比率f(n)/g(n)來重新描述，假設(shè)g(n)最終會大于0。說f=o(g)意味著當n趨于無窮大時，這個比率的極限為0，而f=O(g)表示這個極限是有界的，而f=Q(g)，如果兩個函數(shù)都最終是非0的，則表示f/g和g/f的極限值都是有界的，即f/g的極限值介于兩個固定的正數(shù)之間。如果f=O(g)不成立，則寫成f1O(g)，類似地，得到另外兩個不成立的表示法。f1O(g)意味著不存在常數(shù)C，使得對于所有的n的大值，f(n)<=Cg(n)，換句話說，比率f(n)/g(n)是無界的。一個語句，比