計(jì)算復(fù)雜性類譜圖

張杰　周云才

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

關(guān)鍵詞：計(jì)算復(fù)雜性；復(fù)雜性類；時(shí)間復(fù)雜性；空間復(fù)雜性

中圖分類號(hào)：TP301.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

1 復(fù)雜性分類的起源與意義

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

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

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

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

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

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

在計(jì)算科學(xué)發(fā)展的初期，研究空間復(fù)雜性有重要的意義。因?yàn)槟菚r(shí)的電子技術(shù)不夠發(fā)達(dá)，計(jì)算機(jī)的內(nèi)存資源是寶貴的計(jì)算資源。計(jì)算過程中所需要的存儲(chǔ)資源很容易超出計(jì)算機(jī)所擁有的資源，因而研究如何降低計(jì)算的空間復(fù)雜性成為重要的研究課題[5]。

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

2 幾種重要的復(fù)雜性類

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

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

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

3 復(fù)雜性類之間的關(guān)系

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

根據(jù)時(shí)間譜系定理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的關(guān)系為：NL?P?NP?PSPACE?EXPTIME?EXPSPACE，如圖1。

4 結(jié)束語

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

參考文獻(xiàn)

[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é)議模型與設(shè)計(jì)[M]. 北京： 科學(xué)出版社， 2012： 21-25.

[4] 堵丁柱. 計(jì)算復(fù)雜性理論的近況與展望[J]. 貴州大學(xué)學(xué)報(bào)， 1988， 5（1）： 1-7.

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

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

[7] 高強(qiáng)， 徐心和. 時(shí)間復(fù)雜性和空間復(fù)雜性研究[J]. 智能系統(tǒng)學(xué)報(bào)， 2014， 9（5）： 529-535.

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