理論電腦科學

　　資訊加工的數學理論，又稱為計算理論或電腦科學的數學基礎。

　　計算是資訊加工或資訊活動的過程。反之，在廣泛的意義上講，任何一種形式的資訊加工或資訊的活動(包括大腦的思維活動中的資訊加工和資訊活動）都可以看作是一個計算的過程。資訊的表示與資訊的加工要有一個物質載體，但是並不一定要依賴於某一個特定的載體。不同載體上的資訊活動又有其共性。由於資訊加工的普遍性和相對於載體的獨立性，以資訊加工為研究物件的理論電腦科學必然是一門抽象象的精密科學。它廣泛地采用數學的方法，因此在某種意義下可以看成是數學的一個分支。

　　理論計算機科學最早的分支是20世紀30年代發展起來的可計算性理論。隨著40年代計算機科學技術的迅猛發展，在60年代前後相繼發展瞭自動機與形式語言理論，程序設計和形式語義理論，以及算法分析與計算復雜性理論。這些學科構成瞭目前理論計算機科學的主要內容。它是一門年輕的學科，正在迅速地發展。

　　可計算性理論　計算的本質是什麼？什麼樣的問題是可計算的？什麼樣的問題是不可計算的？這些應當算作是理論計算機科學中最根本的問題。談論問題的可計算性，總是就一個問題類而言的，而這個問題類中原則上應包含無窮多個個別問題。比如說，求兩數的乘積就是一個問題類，求3與7或4與6的乘積則是這類問題中的一些個別問題。說乘法是可計算的，意思是能夠給出一個統一的機械的辦法去解決這個問題類中的任何問題。所謂一個統一的機械的辦法至少應該是：①每一步都是完全確定的。②每一步都是機械地可執行的。③在有限步之內得到答案。④這個統一的辦法本身有一個有窮的描述。這些條件要求計算是一個嚴格精確的過程。但這些條件本身卻是很不精確。為瞭精確地刻畫計算的過程，A.M.圖靈提出瞭一個計算的數學模型，後來被稱為圖靈機器。這個機器由一個有窮的控制器和一條兩邊無限長的帶組成，帶上分成一串方格，每格中可以寫上一個符號。控制器有一個讀寫頭指向帶上某方格，可讀到格中的符號，並把它改寫成另一個符號，還可以左移或右移一格。有窮控制器在任何時刻都處在有窮多個狀態中的某個狀態。它總是根據目前所處的狀態q(∈Q)和讀到的符號α(∈

)決定把這個符號改寫成什麼符號 b(∈ )和自己該轉入哪個狀態 q′(∈ Q)以及讀寫頭是否向左移一格( l)或向右移一格( R)或停留不動( S)。如果開始計算時機器處於開始狀態 q ₀，並把要計算的問題放在帶上，讓機器一步一步地執行下去，最後在帶上就應該得到計算的答案。機器的有窮控制可以用列表的方法表示，表中的每一項都有

q，α→q′，b，D

的形狀，其中 D為 R， l， S之一。這個表就是所謂的統一的機械的辦法，也就是程序。

　　圖靈機器還可以推廣成具有多條帶的圖靈機器。這時它有一條輸入帶，一條輸出帶，k條工作帶。每條帶上有一個讀寫頭聯向有窮控制。它根據當前狀態以及輸入帶和k條工作帶上目前被掃描的符號，決定下一步應轉到什麼狀態，應該在k條工作帶上和輸出帶上寫下什麼符號，以及各個讀寫頭的移動方向。

　　圖靈在設計瞭上述的單帶的模型後提出：凡是可計算的函數都可以用這樣一個機器來實現。這就是著名的圖靈論題。A.丘奇在提出λ演算時也說，可計算的函數都是λ可定義的，這就是丘奇論題。而後S.C.克林證明這兩個論題是等價的，以後稱之為圖靈-丘奇論題。這一論題本身是不能用數學方法加以證明的，隻能夠為歷史所檢驗。半個世紀以來，數學傢提出的各種各樣的合理的計算模型都被證明是和圖靈機器等價的。這一論題已被當作公理一樣地使用著，它不僅是計算機科學的基礎，也是整個數學的基石之一。

　　給瞭一個有窮字母表

後，它上面所有"字"（字母的有限序列）的集合記為 ^*。 ^*的任何子集 l(

^*)稱為 上的一個語言。如果有一個圖靈機 T，使得對於任何輸入字 w∈ ^*， T都在有窮步之內停機，並且停機時， T處於一個特殊的接受狀態 q _α當且僅當 w∈ l，就說 l是可判定的。如果有一個圖靈機 T，從空白帶開始無窮地運行下去，可以把 l中的字一個不漏也不多餘地寫在帶上，就說 l是可枚舉的。

　　可判定的語言一定是可枚舉的。因為如果L中的每個字可判定，就可以依次把屬於l的字枚舉出來。另外，l是可判定的當且僅當l和l在

^*中的補集 ^*- l都是可枚舉的。因為若 l可判定，則 ^*- l當然可判定，因而都是可枚舉的。逆之，若 l和 ^*- l都可枚舉，則不難同時運行兩臺機器，分別枚舉 l和 ^*- l中的字，於是任何輸入字 w，遲早總會被其中一臺枚舉出來。因此總能判定 w是屬於 l還是不屬於 l。

　　不難證明，圖靈機的字母表

中的元素的多少是無關緊要的。一般講，有兩個字母｛0，1｝再加上空格就足夠瞭。每個圖靈機 T的程序總可以用0，1來編碼，記為 C _T。 T從空帶開始運行，枚舉出某些0，1上的字。那麼存在兩種相反的可能性：

　　①T終究會枚舉出C_T；

　　②T永遠不枚舉出C_T。把所有滿足條件(2)的C_T放在一起，構成集合l=｛C_T｜T不枚舉C_T｝。可以斷定l是不可枚舉的。因為若不然，則有一個圖靈機T₀枚舉l。設T₀本身的編碼是C_T0。那麼，T₀是否能枚舉出C_T0呢？如果T₀枚舉C_T0，則C_T0應屬於l，於是T₀不應該枚舉C_T0，矛盾。反之，如果T₀不枚舉C_T0，則C_T0屬於l，於是T₀又應該枚舉C_T0，同樣得到矛盾。所以，枚舉l的圖靈機T₀是根本不能存在的。換言之，l不是可枚舉的，因此更不可判定。以上的證明方法叫做對角線方法。

　　由l的不可判定性出發，可以得到許多數學問題的不可判定性。例如，停機問題不可判定，波斯特字的對應問題不可判定，群上字的問題不可判定，希爾伯特第10問題（代數不定方程是否有解問題，見希爾伯特數學問題）不可判定等等。具有加法和乘法的算術是不可判定的，即不能判定任一給定的算術命題是否為一條定理。謂詞邏輯（見一階邏輯）也是不可判定的。

　　自動機與形式語言理論　一個圖靈機器可以看作為在某種環境下工作的一個有窮控制器。它的環境包括輸入、輸出帶和k條工作帶。如對環境作某些限制，就可得到各種各樣的自動機。

　　如果限制工作帶的總長不超過輸入字的長度，就得到線性有界自動機；限制工作帶的數目k=1，輸入帶頭隻許向右移動，並且工作帶頭右方的符號不保留，就得到棧自動機；限制輸入輸出帶頭都隻能向右移動，並且沒有工作帶，就得到有窮自動機。棧自動機如果要讀工作帶上的一個符號，就必須把其右的符號全部丟掉。這就好象要從子彈夾裡取出一顆子彈就必須先把它上面的子彈全部拿走一樣。如果把工作帶畫成一個子彈夾，棧自動機的工作方式如圖1所示。

　　一個有窮自動機的工作方式則如圖2所示。

　　如果有窮控制器在任何一個時刻，它的下一動作都是完全確定的，就說它是確定型的。否則，如果存在若幹種可能的選擇，就叫做非確定型的。

　　自動機常作為一個語言接受器來研究，這時，輸出帶沒有什麼意義。自動機有若幹個接受狀態。對於確定型的自動機而言，給瞭輸入字w以後，機器一步步動作下去，如果機器最後停機並且停在一個接受狀態，就說機器接受瞭字w，否則就說機器拒絕瞭w。所有被機器接受的字的集合稱為機器接受的語言。對於非確定型的自動機而言，就存在著不同的計算路徑的選擇。有的路通向一個接受的狀態，有的則不然。這時如何定義機器的接受與否，有不同的方式。

　　一種最自然的方式就是：隻要存在一條通向某接受狀態的路，就算機器接受瞭輸入，這種方式一般叫做（狹義的）非確定型。也可以這樣來規定：當所有的路都通向某個接受狀態時才算機器接受瞭輸入，這種方式叫合取型。還可以把所有的狀態分成甲乙兩類，如果機器在甲類狀態有幾種可能的選擇，則隻要求存在一種接受的選擇，如果在乙類狀態有幾種可能的選擇，則要求所有的選擇都是接受的，這種混合情況稱為交錯型。還可以這樣規定：凡碰到有多種可能選擇的情況就用某種隨機的辦法(例如擲骰子)來確定一個選擇，若這樣計算下去達到一個接受狀態的概率大於1/2就認為機器接受w。否則，從接受概率不大於1/2可推出接受概率為0，機器拒絕w。這種類型叫隨機型。合取型、交錯型、隨機型等也都是非確定型。但一般說，非確定型常指狹義的非確定型。

　　自動機在另一個方向上的推廣，就是多個自動機組合成大的自動機，其中各個部分都在不斷地並行工作。這種自動機的研究對於並行計算和模擬生命現象很有意義。硬件可修改機器(HMM)是一個有趣的例子。

　　HMM起初隻有一個細胞，它可以發育成許多個互相聯結在一起的細胞群。每個細胞都是一個完全一樣的有窮自動機。每個細胞在任何時候都處於某個狀態q∈Q，這裡Q是一個有窮的狀態集合。每個細胞有k個突觸，聯向它的“鄰居”，也可以聯向自己。根據它自身的狀態以及它的鄰居的狀態，每個細胞可以做下面幾件事情：

　　①改變到某個新狀態；

　　②把自己的突觸從現在的某鄰居移到該鄰居的某個鄰居（因此變成新的鄰居）；

　　③若有某個突觸指向自己則可以分裂出一個和自己完全一樣的“兒子”，把該突觸指向兒子，兒子的所有突觸指向自己，並令兒子處在某特定狀態。

　　如果把HMM當作一個計算模型，可以假定輸入的字符串是放在一棵二叉樹的葉子上（圖3

），這棵二叉樹的每個結點（圖中用圈表示）都是一個“死的”HMM細胞，即在計算過程中它們的狀態和聯結方式（圖中用雙向箭頭表示）都不變化。隻有樹根上（圖的下方）聯著的那個細胞是“活的”，可以發展成許多細胞，並且把自己的突觸伸到樹葉上（圖的上方）去讀取輸入信息。

　　HMM是具有很強功能的一種模型。如果取消它的第二種功能，再加以種種限制，就得到各種l系統，在描述生命的發展過程時很有用處。如果取消它的第二、三兩種功能，並且假定整個的細胞網絡的編碼由一架圖靈機給出，並且每個細胞都是某個邏輯門，就得到聚合的模型。把它佈線在平面上就得到超大規模集成電路(VLSI)的模型。如果在某一維數的空間格子上佈線，且假定隻有相鄰的格子才有聯系，就得到各種細胞自動機的模型。

　　和自動機理論密切相關的是形式語言理論的研究。1956年，N.喬姆斯基創立瞭形式語法。1960年算法語言ALGOL-60的報告使用瞭巴科斯范式(BNF)來描述。此後形式語言學的研究便蓬勃發展瞭起來。

　　在形式語言學中，一個語法G由四部分組成G=(

， V， S， P)，其中 是字母表； V是和 不相交的變元表； S是 V中的一個變元，稱為初始符號； P是一組產生式，每個產生式都有形狀 α→ β，其中 α和 β都是混合字母表 ∪ V上的一個字， α至少要含有 V中的一個變元，而 β可以是長度為0的空字， α→ β意為用 β來代換 α。這種語法稱為一個0型文法。下面是語法的一個例子：

={ α， b，( ，)，+，*}，

V={S}，

P={S→(S)，S→S+S，S→S*S，S→α，S→b}。

　　從初始符號S出發，不斷用產生式代換，一直到全部由

中的字母組成，就得到一個 上的字。下面是一種可能的代換過程：

S→S*S→S*(S)→S*(S+S)

　　 →α*(S+S)→α*(b+S)→α*(b+α)。

所有能這樣推演出來的字就構成瞭一個語言，叫做該語法所生成的語言。

　　如果限制β的長度不小於α的長度，則得到1型語法（又稱上下文有關語法）；若限制α僅由一個變元組成，則得到2型語法（又稱上下文無關語法）;若再進一步限制產生式右端的β為αB或α 的形式，其中α∈

， B∈ V，則得到3型語法（又稱正規語法）。由0、1、2、3型語法所生成的語言分別稱為0、1、2、3型的語言。它們恰恰是圖靈機器、非確定線性有界自動機、非確定棧自動機、有窮自動機接受的語言。

　　各類語言可以作各種代數運算。例如，求交(l₁∩l₂)，求並(l₁∪l₂)，求補(

^*- l)，克林閉包，同態，代換，商，等等。研究各類語言在代數運算下的封閉性是形式語言理論中的一個方向。

　　給定瞭一個語法之後，自然要問它是否具有某種性質。例如兩個語法是否定義瞭同一個語言?對於0、1、2型語法，這一問題是不可判定的，但對3型語法則是可判定的。在這一方向上有豐富的成果。

　　對於自動機和形式語言的研究，已形成瞭一些抽象的代數理論，例如自動機的半群理論、范疇理論等等，並取得瞭一些積極的成果。

　　程序設計方法與形式語義學　為瞭達到某種目的，如何編出一個程序？編出程序以後又如何證明該程序的確能達到預期的目的？這是一個在實踐中具有十分重要意義的問題。例如要求非負整數x₀和y₀的最大公因子，可以采用下面的程序：

　　符號(x，y)←(x₀，y₀)的意思是同時把x₀和y₀的值賦給x和y。因此若一開始(x₀，y₀)=(6，10)，那麼(x，y)的變化情況為(6，10)→(6，4)→(4，6)→(4，2)→(2，4)→(2，2)→(2，0)→(0，2)。最後輸出y=2，它是6和10的最大公因子。但這個程序為什麼總能給出x₀和y₀的最大公因子並不是很顯然的。另一方面，若把其中

改為

程序就不再是正確的。這是因為對於某些輸入而言，程序不停機。而這一點也不是立即可以看出來的。因此程序的正確性需要證明。

　　所謂證明程序正確，就是要證明：若程序P的輸入滿足某種輸入斷言，則經過P作用之後的輸出滿足某個輸出斷言。在上面的例子中，輸入斷言可表示為

x₀≥0並且y₀≥0並且（x₀≠0或y₀≠0）。

輸出斷言可表示為

。

　　為瞭證明上面程序的正確性，在標號mOre處引進一個不變的性質：

x≥0並且y≥0並且（x≠0或y≠0）

並且

。

然後用歸納法證明每次程序執行到 more時，上面的不變式都成立。因而，執行到 enou H時，就滿足輸出斷言。如果能證明上面的程序的確會停機，就證明瞭它的正確性。

　　數理邏輯對於程序設計方法的應用主要有下面四個方面：

　　① 程序正確性證明；

　　② 停機證明　證明一個程序終於會停機；

　　③ 程序展開　從給定的輸入輸出斷言出發，逐漸構造出一個正確的程序；

　　④ 程序優化　從一個給定的程序出發，構造出一個等價的但更優的程序。

　　以上各方面的研究對程序設計的理論和實踐都有著非常積極的意義。但是另一方面，由於K.哥德爾的不完備性定理，以及不可判定性的結果，以上問題的徹底解決是非常困難的甚至是不可能的。它們的困難程度可從下面的例子看出來。

也就是說，如果整數 x是偶數則除以2，否則乘3再加1。對於小於3× 10 ⁸的所有的數，可以知道最後的 x都會變成1而停機。但是尚不知道，上面的程序是否對於任意的 x都會終止（ x變成1）。

　　為瞭證明程序的正確性，對程序的性質作深入的研究，還發展瞭形式語義學。形式語義學目前主要有操作語義學、指稱語義學、代數語義學和公理語義學等分支。

　　操作語義學把語言的語義看做是在計算系統中所執行的某種操作。這種操作應當被理解為在一種標準的抽象的機器上執行的，而不依賴於一個特定的機器。以算術表達式的求值為例，就是假定瞭一個抽象機器，它有棧區、環境區和控制區三個存儲區。把這三個區中的內容用兩個豎杠分開，再用括號括起來，就表示瞭機器的一個狀態。例如

表示棧區為空，環境區有數據1，2，5分別代表 x ₁， x ₂和 x ₃的當前值，控制區放有符號串( x ₁+ x ₂)* x ₃。算術表達式求值的語義可由下面四大類狀態轉移規則給出：

　　①

　　②

　　③

　　④

其中 St， E， C分別代表棧區、環境區和控制區中的某些內容。第一個式子表示，若控制區的第一串符號是( e ₁， Op， e ₂)或 e ₁ Op e ₂的形狀，其中 e ₁， e ₂是表達式， Op是運算符，那麼把它拆開成 e ₁， e ₂， Op三串符號，放在控制區的前面，其餘內容不動；第二個式子說，若控制區的第一個符號串是某個自然數 n，則把該自然數的表示 n送入棧區的第一個位置；第三個式子說，若控制區的第一個符號串是變元 x _i，則把環境區中第 i個值 e _i放入棧區（因為它代表 x _i的當前值）；最後一個式子說，若控制區的第一串符號是某運算符 Op，則把棧區中前兩個值 m和 n作相應的運算，得到值 m Op n= k，把 k放入棧區第一個位置。

　　上面例子的相應操作如下：

\ n

意為表達式( x ₁+ x ₂)* x ₃在環境 x ₁=1， x ₂=2， x ₃=5下語義為執行上述一系列的操作，最後得到15。

　　在操作語義學中，如果操作的次序不同，盡管操作的結果相同，也被認為具有不同的語義。但在指稱語義學中，結果相同就認為具有相同的語義。所以指稱語義學隻是關心語句引起的狀態的改變。如果用Statements表示所有語句的集合，語義就是一個從Statements到狀態集合State的改變之間的映射，也即一個映射C：

C：Statements→(State→State)。

　　用代數方法和公理化方法研究形式語義，又形成瞭代數語義學和公理語義學。以上四種語義雖然已取得瞭很大進展，但是，隻有操作語義學可以較好地描述程序的語義。

　　復雜性理論和算法分析　可計算性理論在邏輯上的進一步發展，就是計算復雜性理論。著名的圖靈-丘奇論題說，凡是合理的計算模型都是等價的，即一個模型能計算的，在別的模型下也能計算，否則都不可計算。但是對於一個問題類而言，隻知道能不能計算是很不夠的，更有實際意義的是要知道計算需要多少時間，多大的內存等等。由此產生瞭計算復雜性理論和算法分析。

　　計算所需的時間、存儲大小等等都算為資源。嚴格地講，每一種資源的定義都依賴於一個計算模型。各種計算模型的資源的定義雖不一樣，但是主要的有三種。

　　① 串行時間　簡稱時間，它是計算過程中的總運算量。也即把計算分成一些原始的步驟，完成這些步驟所需的總時間。

　　② 空間 它是為瞭保存計算的中間結果所需地盤的大小。例如在計算時用一塊黑板來打草稿，假定每一單位黑板面積可以寫一個符號，且可以擦掉重寫，空間就相當於打草稿所需的黑板面積。

　　③ 並行時間 即並行計算所需的時間。也即多人或多機協同計算，解決一個問題所需要的時間。

　　復雜性總是對於一個特定的問題類來討論的，其中包括無窮多個個別問題，有大有小。例如對矩陣乘法這一問題類而言，相對地說100階矩陣相乘就是一個較大的問題，而二階矩陣相乘則是個較小的問題。所以可以把階n作為衡量問題大小的尺度。但是最一般地，是把輸入的總長度n作為問題大小的尺度。因此，當給定一個算法以後，計算一個大小為n的問題所需的時間、空間等就可以表為n的函數。這個函數就叫做該算法的時間或空間的復雜性之度量，或稱為復雜度。嚴格地講，它是這個特定的問題類在某一特定計算模型中的某一算法下的復雜度。當要解決的問題越來越大時，時間、空間等資源的耗費將以什麼樣的速率增長，也即當n趨於無窮時這個函數增長的階是什麼？這就是復雜性理論所關心的問題。

　　在計算同一個問題類時，算法有好壞之別。例如要判定一個具有n個頂點的無向圖中有沒有回路，早期的算法所需的空間復雜度為S(n)=O(log²n)，但是後來設計瞭更精細的算法，它的空間復雜度隻有O（logn）。這說明O（log²n）隻是早期算法的空間復雜度，而並非這個問題本身的內在復雜度。或者說O（log²n）隻是回路問題空間復雜度的一個上界，而O（logn）則是一個新的更好的上界。對於回路問題，任何算法都至少需要正比於logn的工作空間。這就是說，對於任何算法，空間復雜度S(n)=Ω(logn)。因此可以認為Ω(logn)是回路問題空間復雜度的一個下界。問題內在的復雜度介於上界和下界之間。在這個例子中，二者重合瞭。因此可以說回路問題的空間復雜度正比於logn，記為S(n)=Ⓗ(logn)。

　　又如兩個n位二進整數的乘法在多帶圖靈機模型下，一般的算法需時O(n²)。但改進的算法可以達到O(n^1.5)。現在最好的算法可以達到O(nlognloglogn)。如果采用存儲可修改機器做模型，則可以達到O(n)。可以看出一個問題的內在計算復雜性還因計算模型的不同而有高低。

　　較為重要而且具有特色的計算模型主要有多帶圖靈機器，多帶多維多頭圖靈機器，硬件可修改機器（HMM），隨機存取機器(RAM)，並行隨機存取機器(PRAM)，向量機器，VLSI，等等。然而沒有一個適合一切問題的統一的模型。這樣，復雜性的問題有沒有一個相對統一的標準呢？相似性原理解答瞭這一問題。按此原理，計算一個問題類使用的並行時間、空間和串行時間的復雜程度在所有理想的計算模型中都沒有本質的差異。用數學語言來說，各種模型不僅可以相互模擬而且模擬者所需的並行時間、空間和串行時間都分別不超過被模擬者需用的並行時間、空間和串行時間的一個多項式。所以在隻差一個多項式的范圍內，復雜性還是有其客觀依據而是不依賴於模型的。對於上面提到的各種模型，以及各種計算類型，相似性原理已被證明是正確的。

　　對於串行計算模型都可以定義一個虛擬的並行時間，叫做巡回。所謂巡回，是指計算過程中的周相數。而一個周相則是計算過程中的一個階段，在此階段中新計算出來記在工作空間上的信息不準在同一階段內被讀到。例如，對於多帶圖靈機器而言，一個周相就是工作帶頭不改變方向的一段時間。所以巡回相當於工作帶頭改變方向的總次數。因此可以說，一個問題類有快速的並行算法當且僅當它有一個具有小的巡回數(虛擬並行時間)的串行算法。另外並行時間和空間之間具有某些對稱的性質。例如可以證明，它們之間是多項式相關聯的。所以說，一個問題類有一個快速並行時間算法當且僅當它有一個高度節省內存的算法。

　　既然在多項式關聯意義下復雜性不依賴於模型，就可以用P代表所有具有多項式時間算法的問題類;用NP代表所有具有非確定多項式時間算法的問題類；用NC代表所有能同時在對數多項式並行時間和多項式空間解決的問題類；等等。

　　一般認為，P中的問題才具有現實的可計算性，但有許多實際問題屬於NP，卻未能找到一個確定型多項式時間算法。所以許多人猜想P

N P。1971年庫克在 N P中找到一個問題類，叫做佈爾合取范式的可滿足性問題( S A T)。證明瞭 N P中任何一個問題類的計算均可歸約為 S A T的計算。因此，稱 S A T為一個 N P完全性問題（見 組合最優化）， N P= P當且僅當對 S A T存在一個確定型多項式時間的算法。以後C.卡普等人又把 S A T歸約為許多其他的組合問題，得出瞭許多其他的 N P完全性問題。目前 N P完全性問題幾乎涉及到一切數學的分支，形成瞭一個專門的理論。但是 N P是否等於 P的問題尚未解決。有人猜想它是獨立於現有的數學公理系統的。完全性的研究不限於 N P完全性。對於各個復雜性類，都有完全性問題。

　　在復雜性基本理論的基礎上，對各類具體數學問題的復雜性研究構成瞭算法分析的主要內容，60年代以來取得瞭長足的進展。例如n維的快速傅裡葉變換和n次多項式的乘法，隻需要O(nlogn)次算術運算；n位的數乘在多帶圖靈機上隻需O（nlognloglogn）的時間;判定一個n位數是否為素數需時O(

)；在出度限定情況下，圖同構的判定問題存在多項式時間的算法；判定整系數線性規劃問題是否存在有理解，存在多項式時間算法； n階矩陣乘法隻需4. 7 n ^2.8次算術運算;後來又改進為 O( n )，還證明瞭，這個階可以無窮地改進下去，等等。

　　對比於上界的情況，下界的研究卻碰到瞭許多困難，尤其是對一些具有實際意義的問題。例如對任何一個NP完全性問題，猜想至少需要指數的時間，但多年來連一個非線性的下界都證不出來。

　　除瞭計算的復雜性，還有描述的復雜性，這是Α.Η.柯爾莫哥洛夫和察廷提出來的。一個01串w的信息量I(w)被定義為輸出w的最小程序的長度。因為各個模型可以互相模擬，故以上的定義在隻差一個常數值的意義下，是不依賴於模型的。因為任何一個數學公理系統所包含的信息量是有限的，因而在這個系統中不可能證出I(w)≥с形的定理，這裡с是隻依賴於公理系統的一個常數。但容易知道，除瞭有限多個w以外，所有的w都滿足I(w)≥с（卻無一能被證明）。這一結果簡化和加強瞭哥德爾不完備性定理。