計算複雜性理論

理論計算機科學的分支學科，使用數學方法對計算中所需的各種資源的耗費作定量的分析，並研究各類問題之間在計算複雜程度上的相互關係和基本性質，是演演算法分析的理論基礎。為了計算一類問題，總要耗費一定的時間以及存儲空間等資源。資源耗費的多少決定於被計算問題的大小，是問題大小的函數，稱為問題對該資源需求的複雜度。對複雜度函數增長的階作分析，探討它們對於不同的計算模型在一定意義下的無關性，根據複雜度的階對被計算的問題分類，研究各種不同資源耗費之間的關係，對一些基本問題的資源耗費情況的上、下界作估計等，構成計算複雜性理論的主要研究內容。

數理邏輯和數學本身的發展，在20世紀30年代建立了可計算性理論。40年代以後，隨著計算機科學技術的發展，人們不僅需要研究理論上的、原則上的可計算性，還要研究現實的可計算性，即研究計算一個問題類需要多少時間，多少存儲空間；研究哪些問題是現實可計算的，哪些問題雖然原則上可計算，但由於計算的量太大而實際上無法計算等。這就使得計算複雜性理論作為理論計算機科學的一個分支而發展起來。

計算模型 為了對計算作深入的研究，需要定義一些抽象的機器。30年代所定義的簡單圖靈機、遞歸函數等都是計算的模型。但當時都只考慮到理論上的可計算性而沒有考慮計算的複雜性。因此，為了度量計算的複雜性，70年代前後又提出多帶圖靈機模型、隨機存取機器模型等串列計算模型和向量機器模型等并行計算模型。

資源 資源的確切定義決定於計算的模型。例如，對於多帶的圖靈機，就有串列時間、空間、巡迴等資源(見公理複雜性理論)。一般說來，各種模型的主要資源有并行時間、空間和串列時間三種。

并行時間和巡迴 并行時間一般指并行計算模型計算時所需步數，例如向量機的自始至終執行指令的總條數。但對串列模型也可以定義一種稱為巡迴的資源。可以證明它相當於并行時間。對於多帶圖靈機，它是工作帶頭部改變方向的次數。一般地說，巡迴是周相的總數，而周相則是串列模型工作中的一個階段，在此階段中被計算出來而記錄在工作空間上的信息，在此階段內不再被讀到。

空間 在計算過程中需要記錄下來以備後用的最大中間信息量。對於多帶圖靈機，是計算過程中用過的工作帶上的方格數。

串列時間 計算過程中原始運算的總量。因此，對於串列模型而言，它代表計算自始至終的總步數。對於并行模型而言，每一步可以同時作許多個原始的運算，自始至終各步的原始運算數目的總和就是串列時間。

最壞情況複雜度和平均情況複雜度 在定義任何一種資源時，例如定義時間耗費時，時間是輸入字元串w的函數，記為t(w)。對於所有長度等於n的字w,t(w)中必有最大的一個（可能是無窮大）,這個值只與n有關，可以記為T(n)，稱為最壞情況複雜度。如果考慮對所有長度等於n的字，取t(w)的平均值，就得到平均複雜度。它當然不超過最壞情況複雜度。

相似性原理 對圖靈論題的進一步研究，可斷言各計算模型在計算能力上的大致等價性。也就是說，對於同一類計算問題而言，各理想的計算模型使用本質上同樣多的并行時間、本質上同樣多的空間和本質上同樣多的串列時間，三者同時成立。所謂本質上同樣多是指多項式相關聯。

以多帶圖靈機和向量機器為例，可以證明下面的相似性定理：設n是輸入字元串的長度，它代表問題的大小。對於任何一個多帶圖靈機，設它的巡迴為R(n)，空間為S(n)，串列時間為T(n)，則一定有一個向量機器來模擬它，使得存在一個多項式p，向量機器的并行時間R1(n)，空間S1(n)和串列時間T1(n)滿足

在以上結論中把多帶圖靈機和向量機器的位置對調一下也成立。這說明在多項式相關聯意義下，這兩個模型沒有本質的區別。因此，巡迴是串列模型的虛擬并行時間。

計算的類型 這裡只考慮判定問題或是非問題。機器狀態轉移和接受輸入的方式稱為計算的類型。在普通計算中，機器狀態只依賴於時間和輸入，是完全確定的。每一步都由前一步所達到的狀態惟一確定。如果機器最後進入一個接受狀態，就認為機器接受了輸入。這種計算稱為確定型的，計算的過程可以用一條鏈來表示（圖1）。確定型是最簡單的一種計算類型。

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

隨機型計算的定義有許多種。較弱的一種定義為：從計算樹的根往下走，每到一個岔路口就扔一枚錢幣以決定去向。如果用這種方式碰到一個接受狀態的概率大於，就接受輸入字w。較強的一種定義為：如果輸入應該被拒絕則機器一定拒絕，如果輸入應該被接受則機器接受的概率大於或等於 。或者說，若輸入該被拒絕，機器是不會犯錯誤的；否則機器犯錯誤的可能性不超過一半。這種演演算法又稱為概率演演算法。

R.索羅威和V.史托拉森找到一個多項式時間的隨機型素數判定演演算法。若被判定的數m的確是一個素數，則演演算法一定會回答是素數。若m不是素數，則演演算法回答是素數的可能性小於。可以不斷對m重複這一演演算法，而且每次的結果是獨立的。例如重複100次，若每次回答都是素數則可斷言它是素數，只要有一次回答不是素數則可以肯定它不是素數。這樣，犯錯誤的可能性將小於2。由於尚未找到確定型多項式時間素數判定演演算法，這類概率演演算法就具有很重要的意義。最早的這樣一個演演算法由E.R.伯勒嵌普給出。他找到一個多項式時間的概率演演算法，去分解p個元素的域GF(p)上的一個多項式。

計算理論中有重要意義的計算類型還有交錯型等。

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

複雜性類 根據識別時資源耗費的複雜程度而對形式語言所作的分類。在多項式時間內用確定型機器可識別的語言可歸入一類，記為P。把那些用非確定型機器在多項式的串列時間內可識別的語言歸入一類，記為NP(見NP完全性)。在這種條件下無需說明採用什麼計算模型，因為根據相似性原理，不論採用何種模型,P和NP的意義是不變的。

N.皮彭格提出P的一個重要子類稱為NC,它由所有同時可在多項式的空間和對數多項式的并行時間內可計算的函數組成。如果說P代表現實可計算的問題，那麼NC即代表其中用多項式處理機在對數多項式時間內計算的問題。整數的加減乘除運算、整序、圖聯通性、矩陣的乘法、除法、行列式、多項式的最大公因子、上下文無關語言識別、找圖的最小張開樹等問題都屬於NC。

與之對偶的另一個子類由所有同時可在多項式的并行時間和對數多項式的空間內計算的函數所組成，稱為SC。

在確定型多項式空間中可判定的語言類記為pSpace。就已有的計算模型而言，在確定型多項式并行時間中可判定的語言類恰為PSPACE。

當然，還可以考慮概率型的機器在對數多項式并行時間和多項式空間中可識別的語言類等。根據相似性原理，這些類的定義都是獨立於計算模型的。

歸約和完全性 研究複雜性類和其間關係的方法。在數學中，常常把一類問題的計算歸結為另一類問題的計算。例如，利用公式

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

設有兩個語言L1、L2和一個簡單易行的變換T,如果一個字X屬於L1,當且僅當變換以後的字T(x)屬於L2,那麼就說變換T 把L1歸約成L2。因為，若要判定某個字X 是否屬於L1,只要用T 變換一下，然後去判斷T(x)是否屬於L2就行了。為了使得歸約是有實際意義的，就要求T是一個容易實現的變換。例如，可在對數空間中實現。這時就說L1在對數空間中歸約為L2。

設C是一個複雜性類，L是任一語言。如果 C中任何語言都可以在對數空間中歸約為L，就說C可在對數空間中歸約為L。或者說,L屬於C 難。其直觀意義為：若L可以容易地計算出來，則C 中任何問題均可以容易地計算出來。反之，若C 中有難於識別的問題，則L的識別肯定不會更容易（故稱為C 難）。進一步說，如果L屬於C 難，而且本身也屬於C,就說L在C 中是完全的。意意是:C 中任何語言可以很快識別，當且僅當人可以很快識別。

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

複雜度的上界和下界 用以估計問題所需某資源的複雜程度的界限函數。如果找到解某問題的演演算法，其資源的複雜度為u(n)，則u(n)是問題本身複雜度的一個上界。如果對任何演演算法，其複雜度都必需大於l(n),則l(n)是問題複雜度的一個下界。

對各類具體問題的複雜度的上、下界的研究，一般說來屬於演演算法分析的範圍。但有時也把某些基本問題的上、下界的研究歸入複雜性理論。

n維的快速傅里葉變換需要O(n logn )次算術運算；n位的乘法在多帶圖靈機上需時O(n log n log log n)；n階矩陣乘法只需要4.7n次算術運算，判定一個n位數是否為素數需時O(2.81);在出度限定情形下的圖同構的判定，存在多項式時間演演算法。

下界的結果多藉助於對角線方法得出，最典型的是關於複雜性譜系的一系列結果。帶有平方的正規表達式的等價問題的判定需要指數的空間。例如，不難證明，為了把n個數排序，比較的次數至少正比於nlogn。又如n個點的多項式的插值問題，若只許用算術運算，則至少需要nlogn次乘法。關於兩個資源乘積的下界，為了識別n 位的完全平方數，在一個離線的圖靈機上，時間和空間的乘積至少正比於n2。為了對n 個大小從1到n2之間的數排序，時間和空間的乘積至少正比於。為了識別任何非正規的語言，多帶圖靈機的工作空間和工作帶巡迴數的乘積的階不能小於n。

從發展趨勢來看，計算複雜性理論將深入到各個數學分支中去。計算機科學的發展，特別是新一代計算機系統和人工智慧的研究，又會給計算複雜性理論提出許多新的課題。計算複雜性理論、描述複雜性理論、資訊理論、數理邏輯等學科將有可能更緊密結合，得到有關信息加工或信息活動的一些深刻結論。

參考書目

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.