[拼音]：jisuan fuzaxing lilun

[外文]：computational complexity theory

理論計(jì)算機(jī)科學(xué)的分支學(xué)科，使用數(shù)學(xué)方法對(duì)計(jì)算中所需的各種資源的耗費(fèi)作定量的分析，并研究各類問(wèn)題之間在計(jì)算復(fù)雜程度上的相互關(guān)系和基本性質(zhì)，是算法分析的理論基礎(chǔ)。為了計(jì)算一類問(wèn)題，總要耗費(fèi)一定的時(shí)間以及存儲(chǔ)空間等資源。資源耗費(fèi)的多少?zèng)Q定于被計(jì)算問(wèn)題的大小，是問(wèn)題大小的函數(shù)，稱為問(wèn)題對(duì)該資源需求的復(fù)雜度。對(duì)復(fù)雜度函數(shù)增長(zhǎng)的階作分析，探討它們對(duì)于不同的計(jì)算模型在一定意義下的無(wú)關(guān)性，根據(jù)復(fù)雜度的階對(duì)被計(jì)算的問(wèn)題分類，研究各種不同資源耗費(fèi)之間的關(guān)系，對(duì)一些基本問(wèn)題的資源耗費(fèi)情況的上、下界作估計(jì)等，構(gòu)成計(jì)算復(fù)雜性理論的主要研究?jī)?nèi)容。

數(shù)理邏輯和數(shù)學(xué)本身的發(fā)展，在20世紀(jì)30年代建立了可計(jì)算性理論。40年代以后，隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，人們不僅需要研究理論上的、原則上的可計(jì)算性，還要研究現(xiàn)實(shí)的可計(jì)算性，即研究計(jì)算一個(gè)問(wèn)題類需要多少時(shí)間，多少存儲(chǔ)空間；研究哪些問(wèn)題是現(xiàn)實(shí)可計(jì)算的，哪些問(wèn)題雖然原則上可計(jì)算，但由于計(jì)算的量太大而實(shí)際上無(wú)法計(jì)算等。這就使得計(jì)算復(fù)雜性理論作為理論計(jì)算機(jī)科學(xué)的一個(gè)分支而發(fā)展起來(lái)。

計(jì)算模型

為了對(duì)計(jì)算作深入的研究，需要定義一些抽象的機(jī)器。30年代所定義的簡(jiǎn)單圖靈機(jī)、遞歸函數(shù)等都是計(jì)算的模型。但當(dāng)時(shí)都只考慮到理論上的可計(jì)算性而沒(méi)有考慮計(jì)算的復(fù)雜性。因此，為了度量計(jì)算的復(fù)雜性，70年代前后又提出多帶圖靈機(jī)模型、隨機(jī)存取機(jī)器模型等串行計(jì)算模型和向量機(jī)器模型等并行計(jì)算模型。

資源

資源的確切定義決定于計(jì)算的模型。例如，對(duì)于多帶的圖靈機(jī)，就有串行時(shí)間、空間、巡回等資源(見(jiàn)公理復(fù)雜性理論)。一般說(shuō)來(lái)，各種模型的主要資源有并行時(shí)間、空間和串行時(shí)間三種。

并行時(shí)間和巡回

并行時(shí)間一般指并行計(jì)算模型計(jì)算時(shí)所需步數(shù)，例如向量機(jī)的自始至終執(zhí)行指令的總條數(shù)。但對(duì)串行模型也可以定義一種稱為巡回的資源。可以證明它相當(dāng)于并行時(shí)間。對(duì)于多帶圖靈機(jī)，它是工作帶頭部改變方向的次數(shù)。一般地說(shuō)，巡回是周相的總數(shù)，而周相則是串行模型工作中的一個(gè)階段，在此階段中被計(jì)算出來(lái)而記錄在工作空間上的信息，在此階段內(nèi)不再被讀到。

空間

在計(jì)算過(guò)程中需要記錄下來(lái)以備后用的最大中間信息量。對(duì)于多帶圖靈機(jī)，是計(jì)算過(guò)程中用過(guò)的工作帶上的方格數(shù)。

串行時(shí)間

計(jì)算過(guò)程中原始運(yùn)算的總量。因此，對(duì)于串行模型而言，它代表計(jì)算自始至終的總步數(shù)。對(duì)于并行模型而言，每一步可以同時(shí)作許多個(gè)原始的運(yùn)算，自始至終各步的原始運(yùn)算數(shù)目的總和就是串行時(shí)間。

最壞情況復(fù)雜度和平均情況復(fù)雜度

在定義任何一種資源時(shí)，例如定義時(shí)間耗費(fèi)時(shí)，時(shí)間是輸入字符串w的函數(shù)，記為t(w)。對(duì)于所有長(zhǎng)度等于n的字w，t(w)中必有最大的一個(gè)（可能是無(wú)窮大），這個(gè)值只與n有關(guān)，可以記為T(n)，稱為最壞情況復(fù)雜度。如果考慮對(duì)所有長(zhǎng)度等于n的字，取t(w)的平均值，就得到平均復(fù)雜度。它當(dāng)然不超過(guò)最壞情況復(fù)雜度。

相似性原理

對(duì)圖靈論題的進(jìn)一步研究，可斷言各計(jì)算模型在計(jì)算能力上的大致等價(jià)性。也就是說(shuō)，對(duì)于同一類計(jì)算問(wèn)題而言，各理想的計(jì)算模型使用本質(zhì)上同樣多的并行時(shí)間、本質(zhì)上同樣多的空間和本質(zhì)上同樣多的串行時(shí)間，三者同時(shí)成立。所謂本質(zhì)上同樣多是指多項(xiàng)式相關(guān)聯(lián)。

以多帶圖靈機(jī)和向量機(jī)器為例，可以證明下面的相似性定理：設(shè)n是輸入字符串的長(zhǎng)度，它代表問(wèn)題的大小。對(duì)于任何一個(gè)多帶圖靈機(jī)，設(shè)它的巡回為R(n)，空間為S(n)，串行時(shí)間為T(n)，則一定有一個(gè)向量機(jī)器來(lái)模擬它，使得存在一個(gè)多項(xiàng)式p，向量機(jī)器的并行時(shí)間R₁(n)，空間S₁(n)和串行時(shí)間T₁(n)滿足

R₁(n)≤p(R(n))

S₁(n)≤p(S(n))

T₁(n)≤p(T(n))

在以上結(jié)論中把多帶圖靈機(jī)和向量機(jī)器的位置對(duì)調(diào)一下也成立。這說(shuō)明在多項(xiàng)式相關(guān)聯(lián)意義下，這兩個(gè)模型沒(méi)有本質(zhì)的區(qū)別。因此，巡回是串行模型的虛擬并行時(shí)間。

計(jì)算的類型

這里只考慮判定問(wèn)題或是非問(wèn)題。機(jī)器狀態(tài)轉(zhuǎn)移和接受輸入的方式稱為計(jì)算的類型。在普通計(jì)算中，機(jī)器狀態(tài)只依賴于時(shí)間和輸入，是完全確定的。每一步都由前一步所達(dá)到的狀態(tài)惟一確定。如果機(jī)器最后進(jìn)入一個(gè)接受狀態(tài)，就認(rèn)為機(jī)器接受了輸入。這種計(jì)算稱為確定型的，計(jì)算的過(guò)程可以用一條鏈來(lái)表示（圖1）。確定型是最簡(jiǎn)單的一種計(jì)算類型。

但有時(shí)機(jī)器在某一時(shí)刻可以有若干種選擇，進(jìn)入若干不同狀態(tài)，而在新的情況下又有若干不同選擇等。這時(shí)計(jì)算過(guò)程可用一棵樹(shù)表示(圖2)。若規(guī)定只要有一條路從樹(shù)根通向一個(gè)接受的頂點(diǎn)，就認(rèn)為機(jī)器接受了輸入字符串，這種接受方式就叫作非確定型的（見(jiàn)非確定性）。此時(shí)，樹(shù)高被看作是非確定計(jì)算所需的時(shí)間。

隨機(jī)型計(jì)算的定義有許多種。較弱的一種定義為:從計(jì)算樹(shù)的根往下走，每到一個(gè)岔路口就扔一枚錢幣以決定去向。如果用這種方式碰到一個(gè)接受狀態(tài)的概率大于1/2，就接受輸入字w。較強(qiáng)的一種定義為：如果輸入應(yīng)該被拒絕則機(jī)器一定拒絕，如果輸入應(yīng)該被接受則機(jī)器接受的概率大于或等于 1/2。或者說(shuō)，若輸入該被拒絕，機(jī)器是不會(huì)犯錯(cuò)誤的；否則機(jī)器犯錯(cuò)誤的可能性不超過(guò)一半。這種算法又稱為概率算法。

R.索羅威和V.史托拉森找到一個(gè)多項(xiàng)式時(shí)間的隨機(jī)型素?cái)?shù)判定算法。若被判定的數(shù)m的確是一個(gè)素?cái)?shù)，則算法一定會(huì)回答是素?cái)?shù)。若m不是素?cái)?shù)，則算法回答是素?cái)?shù)的可能性小于1/2?？梢圆粩鄬?duì)m重復(fù)這一算法，而且每次的結(jié)果是獨(dú)立的。例如重復(fù)100次，若每次回答都是素?cái)?shù)則可斷言它是素?cái)?shù)，只要有一次回答不是素?cái)?shù)則可以肯定它不是素?cái)?shù)。這樣，犯錯(cuò)誤的可能性將小于2。由于尚未找到確定型多項(xiàng)式時(shí)間素?cái)?shù)判定算法，這類概率算法就具有很重要的意義。最早的這樣一個(gè)算法由E.R.伯勒嵌普給出。他找到一個(gè)多項(xiàng)式時(shí)間的概率算法，去分解p個(gè)元素的域GF(p)上的一個(gè)多項(xiàng)式。

計(jì)算理論中有重要意義的計(jì)算類型還有交錯(cuò)型等。

相似性原理和相似性定理不僅對(duì)確定型計(jì)算成立，而且對(duì)非確定型、交錯(cuò)型、隨機(jī)型等各種計(jì)算類型都是成立的。

復(fù)雜性類

根據(jù)識(shí)別時(shí)資源耗費(fèi)的復(fù)雜程度而對(duì)形式語(yǔ)言所作的分類。在多項(xiàng)式時(shí)間內(nèi)用確定型機(jī)器可識(shí)別的語(yǔ)言可歸入一類，記為P。把那些用非確定型機(jī)器在多項(xiàng)式的串行時(shí)間內(nèi)可識(shí)別的語(yǔ)言歸入一類，記為NP(見(jiàn)NP完全性)。在這種條件下無(wú)需說(shuō)明采用什么計(jì)算模型，因?yàn)楦鶕?jù)相似性原理，不論采用何種模型，P和NP的意義是不變的。

N.皮彭格提出P的一個(gè)重要子類稱為NC，它由所有同時(shí)可在多項(xiàng)式的空間和對(duì)數(shù)多項(xiàng)式的并行時(shí)間內(nèi)可計(jì)算的函數(shù)組成。如果說(shuō)P代表現(xiàn)實(shí)可計(jì)算的問(wèn)題，那么NC即代表其中用多項(xiàng)式處理機(jī)在對(duì)數(shù)多項(xiàng)式時(shí)間內(nèi)計(jì)算的問(wèn)題。整數(shù)的加減乘除運(yùn)算、整序、圖聯(lián)通性、矩陣的乘法、除法、行列式、多項(xiàng)式的最大公因子、上下文無(wú)關(guān)語(yǔ)言識(shí)別、找圖的最小張開(kāi)樹(shù)等問(wèn)題都屬于NC。

與之對(duì)偶的另一個(gè)子類由所有同時(shí)可在多項(xiàng)式的并行時(shí)間和對(duì)數(shù)多項(xiàng)式的空間內(nèi)計(jì)算的函數(shù)所組成，稱為SC。

在確定型多項(xiàng)式空間中可判定的語(yǔ)言類記為PSPACE。就已有的計(jì)算模型而言，在確定型多項(xiàng)式并行時(shí)間中可判定的語(yǔ)言類恰為PSPACE。

當(dāng)然，還可以考慮概率型的機(jī)器在對(duì)數(shù)多項(xiàng)式并行時(shí)間和多項(xiàng)式空間中可識(shí)別的語(yǔ)言類等。根據(jù)相似性原理，這些類的定義都是獨(dú)立于計(jì)算模型的。

歸約和完全性

研究復(fù)雜性類和其間關(guān)系的方法。在數(shù)學(xué)中，常常把一類問(wèn)題的計(jì)算歸結(jié)為另一類問(wèn)題的計(jì)算。例如，利用公式

可把乘法歸約為平方、加減法和用2 除。如果平方、加減法和用2除能很快算出來(lái)，乘法也就可以很快地算出來(lái)。

設(shè)有兩個(gè)語(yǔ)言L₁、L₂和一個(gè)簡(jiǎn)單易行的變換T，如果一個(gè)字X屬于L₁，當(dāng)且僅當(dāng)變換以后的字T(x)屬于L₂，那么就說(shuō)變換T 把L₁歸約成L₂。因?yàn)?，若要判定某個(gè)字X 是否屬于L₁，只要用T 變換一下，然后去判斷T(x)是否屬于L₂就行了。為了使得歸約是有實(shí)際意義的，就要求T是一個(gè)容易實(shí)現(xiàn)的變換。例如，可在對(duì)數(shù)空間中實(shí)現(xiàn)。這時(shí)就說(shuō)L₁在對(duì)數(shù)空間中歸約為L₂。

設(shè)C是一個(gè)復(fù)雜性類，L是任一語(yǔ)言。如果 C中任何語(yǔ)言都可以在對(duì)數(shù)空間中歸約為L，就說(shuō)C可在對(duì)數(shù)空間中歸約為L?；蛘哒f(shuō)，L屬于C 難。其直觀意義為：若L可以容易地計(jì)算出來(lái)，則C 中任何問(wèn)題均可以容易地計(jì)算出來(lái)。反之，若C 中有難于識(shí)別的問(wèn)題，則L的識(shí)別肯定不會(huì)更容易（故稱為C 難）。進(jìn)一步說(shuō)，如果L屬于C 難，而且本身也屬于C，就說(shuō)L在C 中是完全的。意意是:C 中任何語(yǔ)言可以很快識(shí)別，當(dāng)且僅當(dāng)人可以很快識(shí)別。

歸約和完全性是復(fù)雜性理論中重要的研究方法。第一個(gè)NP完全性問(wèn)題由S.A.庫(kù)克在1971年提出，R.卡爾普等人解決了一系列基本的NP完全性問(wèn)題。

復(fù)雜度的上界和下界

用以估計(jì)問(wèn)題所需某資源的復(fù)雜程度的界限函數(shù)。如果找到解某問(wèn)題的算法，其資源的復(fù)雜度為u(n)，則u(n)是問(wèn)題本身復(fù)雜度的一個(gè)上界。如果對(duì)任何算法，其復(fù)雜度都必需大于l(n)，則l(n)是問(wèn)題復(fù)雜度的一個(gè)下界。

對(duì)各類具體問(wèn)題的復(fù)雜度的上、下界的研究，一般說(shuō)來(lái)屬于算法分析的范圍。但有時(shí)也把某些基本問(wèn)題的上、下界的研究歸入復(fù)雜性理論。

n維的快速傅里葉變換需要O(n logn )次算術(shù)運(yùn)算；n位的乘法在多帶圖靈機(jī)上需時(shí)O(n log n log log n)；n階矩陣乘法只需要4.7n次算術(shù)運(yùn)算，判定一個(gè)n位數(shù)是否為素?cái)?shù)需時(shí)O();在出度限定情形下的圖同構(gòu)的判定，存在多項(xiàng)式時(shí)間算法。

下界的結(jié)果多借助于對(duì)角線方法得出，最典型的是關(guān)于復(fù)雜性譜系的一系列結(jié)果。帶有平方的正規(guī)表達(dá)式的等價(jià)問(wèn)題的判定需要指數(shù)的空間。例如，不難證明，為了把n個(gè)數(shù)排序，比較的次數(shù)至少正比于nlogn。又如n個(gè)點(diǎn)的多項(xiàng)式的插值問(wèn)題，若只許用算術(shù)運(yùn)算，則至少需要nlogn次乘法。關(guān)于兩個(gè)資源乘積的下界，為了識(shí)別n 位的完全平方數(shù)，在一個(gè)離線的圖靈機(jī)上，時(shí)間和空間的乘積至少正比于n²。為了對(duì)n 個(gè)大小從1到n²之間的數(shù)排序，時(shí)間和空間的乘積至少正比于n²/logn。為了識(shí)別任何非正規(guī)的語(yǔ)言，多帶圖靈機(jī)的工作空間和工作帶巡回?cái)?shù)的乘積的階不能小于n。

從發(fā)展趨勢(shì)來(lái)看，計(jì)算復(fù)雜性理論將深入到各個(gè)數(shù)學(xué)分支中去。計(jì)算機(jī)科學(xué)的發(fā)展，特別是新一代計(jì)算機(jī)系統(tǒng)和人工智能的研究，又會(huì)給計(jì)算復(fù)雜性理論提出許多新的課題。計(jì)算復(fù)雜性理論、描述復(fù)雜性理論、信息論、數(shù)理邏輯等學(xué)科將有可能更緊密結(jié)合，得到有關(guān)信息加工或信息活動(dòng)的一些深刻結(jié)論。

參考書目

1. A.V. Aho， J.E.Hopcroft & J.D.Ullman，The Design and　Analysis　of　Computer Algorithms， Addison-Wesley，Reading，Mass.，1974.
2. J. E. Hopcroft， & J.D. Ullman， Introduction to Automata　Theory，Languages　and　Computation，Addison-Wesley，Reading，Mass.，1979.

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：計(jì)算復(fù)雜性理論

版權(quán)聲明：本文采用知識(shí)共享 署名4.0國(guó)際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《計(jì)算復(fù)雜性理論》

文章鏈接：http://m.fjemb.com/14141.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識(shí)整合。如若侵權(quán)請(qǐng)通過(guò)投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。