張杰　周云才

摘要：一個問題的計算復雜性（complexity）是指用計算機解決它的復雜程度，其度量標準：一是計算所需的步數(shù)或指令條數(shù)（即時間復雜度），二是計算所需的存儲單元數(shù)（即空間復雜度）。復雜度相似的所有問題構成的集合就是一個復雜性類（complexity class）。該文探討了在計算復雜性理論中常見的幾種比較重要的計算復雜性類，研究了對計算復雜性歸類的重要意義，以及復雜性類之間的一些關聯(lián)。

關鍵詞：計算復雜性；復雜性類；時間復雜性；空間復雜性

中圖分類號：TP301.5 文獻標識碼：A 文章編號：1009-3044（2015）24-0040-03

Class Spectrogram of Computational Complexity

ZHANG Jie，ZHOU Yun-cai

（Computer Science College of Yangtze University，Jingzhou 434023，China）

Abstract：The computational complexity of a problem is the complexity of solving it with a computer.One of its measures is to calculate the required number of steps or instructions （that is， the time complexity），the other is to calculate the number of storage unit （i.e.， space complexity）.The set of all the problems with similar complexity is a complexity class.In this paper，we discussed several common and important computational complexity classes in computational complexity theory，and studied the significance of the classification of computational complexity and some relations between the complexity classes.

Keywords：computational complexity；complexity class；time complexity；space complexity

計算復雜性理論是一門研究求解計算問題所需要的時間、存貯量，或者其它資源的理論[1]。計算復雜性的概念，源于20世紀30年代數(shù)學邏輯的一些深刻命題。所謂計算復雜性，通俗說來，就是用計算機求解問題的難易程度。將計算問題按照在不同計算模型下所需資源的不同予以分類，從而得到一個對算法問題“難度”的類別，就是復雜性理論中復雜性類概念的來源[2]。

在計算復雜度理論中，通常情況下，不可能也不必要就一個個具體問題去研究它的計算復雜性，而是依據(jù)難度去研究各種計算問題之間的聯(lián)系，按復雜性把問題分成不同的類，即計算復雜性類[3]。通常我們喜歡用圖靈機（Turing）定義復雜性類，圖靈機是種抽象計算機[4]。一個典型的復雜度類的定義有以下形式：可以被同一個抽象機器M使用O（f（n））的資源R所解決的問題的集合（n是輸入數(shù)據(jù)的大?。?。

1 復雜性分類的起源與意義

算法復雜性分析的一個早期的例子是1844年Gabriel Lamé所做的歐幾里得算法的運行時間分析。在實際研究開始明確地致力于算法問題的復雜度之前，各種多樣研究奠定了許多基礎，其中最有影響力的是1936年圖靈（Alan Turing）定義的圖靈機，它是一個非常強大且靈活的簡化計算機模型。

Fortnow & Homer （2003）表明計算復雜性的系統(tǒng)性研究開始于尤里斯·哈特馬尼斯（Juris Hartmanis）和理查德·斯特恩（Richard Stearns）在1965年發(fā)表的開創(chuàng)性論文“關于算法的計算復雜性”，它奠定了時間和空間復雜度的定義以及證明了層次結構定理。同時在1965年，埃德蒙茲（Edmonds）定義了一個“好”的算法，運行時間由輸入規(guī)模的多項式來界定。

據(jù)Fortnow & Homer （2003），早期的研究特定有限資源圖靈機可以解決的問題的論文包括約翰·邁希爾（John Myhill）的線性有界自動機的定義（Myhill 1960），雷蒙德·史慕揚（Raymond Smullyan）的基本集的研究（1961），以及山田·尚勇（Hisao Yamada）的關于實時計算的論文（1962）。更早一些的時候，來自蘇聯(lián)的該領域的先驅鮑里斯（Boris Trakhtenbrot）（1956）研究了另一種特殊的復雜性度量。

1967年，曼紐爾·布盧姆（Manuel Blum）發(fā)表了一個基于他的公理的不言自明的復雜性理論并證明了一個重要的結論，即所謂的加速定理。該領域真正開始蓬勃發(fā)展是在1971年的時候，美國的研究員斯蒂芬·庫克（Stephen Cook）和蘇聯(lián)的列昂尼德·萊文（Leonid Levin） 獨立證明了存在切實相關的問題——NP完全性。1972年，理查德·卡普（Richard Karp）在他的里程碑式的論文“組合問題中的還原性”中給這個想法帶來了飛躍 ，他在論文中展示了21個多元組合與圖論問題，每一個都因其計算棘手而聞名，即是NP完全性。

自1971年Cook發(fā)表了他的著名定理以來，計算復雜性理論發(fā)展得相當快。已經(jīng)形成了錯綜復雜的許多方向[4]。

研究問題的計算復雜性，可以明確該問題是否存在有效的求解算法[7]，如果它被證明是難解的，就不必將大量精力花費在尋找有效的求解算法上[1]，從而在實際工作中做出理性的抉擇。某些計算問題在理論上是可解的，但是解決需要耗費大量的時間或空間，以至于無法在實踐中應用[1]。

在計算科學發(fā)展的初期，研究空間復雜性有重要的意義。因為那時的電子技術不夠發(fā)達，計算機的內(nèi)存資源是寶貴的計算資源。計算過程中所需要的存儲資源很容易超出計算機所擁有的資源，因而研究如何降低計算的空間復雜性成為重要的研究課題[5]。

首先將計算復雜性嚴格地建立在可計算性理論基礎上的是Hartmanis和Stearns，他們受形式語言理論的啟發(fā)，以多帶Turing機為計算模型嚴格地給出了復雜性類P的定義，并且建立了確定型的時間類的分層定理[6]。

2 幾種重要的復雜性類

當人們使用計算機解問題時，最關心的參量有兩個，即計算時間和存儲空間。這兩個參量反映到計算復雜性理論中就成為了時間復雜性和空間復雜性的概念[4]。因為算法的精確的運行時間通常是一個復雜的表達式，所以一般只是估計它，只考慮算法運行時間的表達式的最高次項，而忽略該項的系數(shù)和其它低次項，這種記法稱為大O記法[1]，通常采用大O記法來描述算法運行時所需資源。在圖靈機的計算模型中分為確定性圖靈機和非確定性圖靈機，一些問題可用確定性圖靈機來描述，而有些問題更適于采用非確定性圖靈機來描述。根據(jù)解決問題所需時間和空間資源的層次不同，可將問題歸為幾種不同的復雜性類，詳見表1。

表1中的PSPACE這個類的名字可以看作是由P（多項式）+Space（空間）定義的。具體地說，PSPACE類是在圖靈機上用多項式數(shù)量的工作比特，在不限制時間的情況下可以求解的問題類[3]。其它類也可依此描述，這里不再贅述。

檢查兩個數(shù)是否互素的問題屬于P類；有向圖G包含節(jié)點s和t，PATH問題要確定是否存在從s到t的有向路徑，PATH∈P。判定一個無向圖中是否包含指定大小的團屬于NP類。判定一個全量詞化的布爾公式是真還是假問題屬于PSPACE。語言A={0k1k|k≥0}是L的成員。

3 復雜性類之間的關系

事實上，P類是包含在PSPACE類中的，即P?PSPACE。因為在多項式時間內(nèi)，停機的圖靈機只能訪問多項式數(shù)量的方格（空間或工作比特）[3]。另外，NP也是PSPACE類的子集，NP?PSPACE。P是在確定型圖靈機上以多項式時間求解的問題的集合；NP是在非確定型圖靈機上以多項式時間求解的問題的集合；NP問題若在確定型圖靈機上求解，就需要用確定型圖靈機去模擬非確定型圖靈機的運行過程，這種模擬所需要的時間是指數(shù)級的，因此，普遍認為NP問題要難于P類問題，即P?NP[8]。同P≠NP問題類似，至今為止，仍然不知道P≠PSPACE是否成立，即仍然無法確定PSPACE類中是否包含不在P類中的問題[3]。

根據(jù)時間譜系定理DTIME（f（n））?DTIME（f（n）·log2（f（n）））和空間譜系定理DSPACE（f（n））?DSPACE（f（n）·log（f（n）））有：P ?EXPTIME 且NP ?NEXPTIME 且PSPACE ? EXPSPACE。另外，已經(jīng)證明PSPACE和NL、P、NP、EXPTIME和EXPSPACE的關系為：NL?P?NP?PSPACE?EXPTIME?EXPSPACE，如圖1。

4 結束語

計算復雜性理論為許多實際應用中的可解不可解問題提供了很好的理論基礎，而計算復雜性類亦為判斷求解某一具體問題的難易程度提供了直接的依據(jù)，所以研究算法復雜性和計算復雜性類具有十分重要的意義。除了以上提到的常見重要復雜性類之外，還有另外一些依照不同的分類標準而形成的其他復雜性類，例如：BPP、ZPP、RP、AC、NC、BQP、QMA、#P、IP、AM、ALL等，文章在這里就不再詳細敘述。此外，在計算復雜性理論中還存在著至今依然懸而未決的問題，例如：還不知道coNP是否與NP不同（coNP包括NP中的語言的補語言），不確定P=NP是否成立，不知道coNL ?P和P ?PSPACE哪一個成立。有興趣的讀者可以自行研究探索上述問題。

參考文獻

[1] Sipser M. Introduction to the theory of computation[M].Beijing： China Machine Press， 2000： 147-197.

[2] Wikipedia contributors. Computational complexity theory[G/OL].http：//en.wikipedia.org/w/index.php？title=Computational_ complexity_theory&oldid=649895389，2015-03-04/2015-03-31.

[3] 劉天華， 朱宏峰. 安全協(xié)議模型與設計[M]. 北京： 科學出版社， 2012： 21-25.

[4] 堵丁柱. 計算復雜性理論的近況與展望[J]. 貴州大學學報， 1988， 5（1）： 1-7.

[5] 李順東， 王道順. 現(xiàn)代密碼學： 理論、 方法與研究前沿[M].北京： 科學出版社， 2009： 35-41.

[6] 堵丁柱.計算復雜性對運籌學發(fā)展的影響[J]. 運籌學雜志， 1989， 8（1）： 7-11.

[7] 高強， 徐心和. 時間復雜性和空間復雜性研究[J]. 智能系統(tǒng)學報， 2014， 9（5）： 529-535.

[8] Papadimiriou C. Computational Complexity[M]. Reading， Massachusetts： Addison-Wesley， 1994： 491-493.