計(jì)算復(fù)雜性理論
[拼音]: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í)間R1(n),空間S1(n)和串行時(shí)間T1(n)滿足
R1(n)≤p(R(n))
S1(n)≤p(S(n))
T1(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ǔ)言L1、L2和一個(gè)簡(jiǎn)單易行的變換T,如果一個(gè)字X屬于L1,當(dāng)且僅當(dāng)變換以后的字T(x)屬于L2,那么就說(shuō)變換T 把L1歸約成L2。因?yàn)?,若要判定某個(gè)字X 是否屬于L1,只要用T 變換一下,然后去判斷T(x)是否屬于L2就行了。為了使得歸約是有實(shí)際意義的,就要求T是一個(gè)容易實(shí)現(xiàn)的變換。例如,可在對(duì)數(shù)空間中實(shí)現(xiàn)。這時(shí)就說(shuō)L1在對(duì)數(shù)空間中歸約為L2。
設(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í)間和空間的乘積至少正比于n2。為了對(duì)n 個(gè)大小從1到n2之間的數(shù)排序,時(shí)間和空間的乘積至少正比于n2/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é)論。
- 參考書目
-
- A.V. Aho, J.E.Hopcroft & J.D.Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley,Reading,Mass.,1974.
- 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í)處理。