複雜性理論與現實計算的關係
開始我們先引用他的一段話，他說：“在理論計算機科學中，我們犯了像純數學家那樣行事的錯誤，數學家的指南是不能永遠引導我們去很好地研究和探索計算機科學的。我們時常將關於計算的證明難度看得比這些已證明的結果中的思想還重。我們已經沉醉於數學的優美性而且為抽象本身而去追求抽象，我們往往對一些小問題並且可能是不相幹的問題花很多時間來進行理智的搏鬥，而不是去建立和發展直接和計算有關的新理論《論理論計算機科學的發展》康乃爾大學技術報告）。
這裏，要求我們注意、在理論計算機科學中，哪些結果是和實際計算有關或者是無關的。在本文中，我們將限於討論複雜性理論與實際計算的關係問題。
複雜性理論（這裏指計算複雜性理論）是由抽象理論派生出來的，而抽象複雜性理論是可計算性理論。後者是研究有關計算的一般性問題的（也就是關於在理想計算機上進行計算的問題前者是研究有關可行計算的問題（也就是關於在計算時間和存貯空間都有限製的機器上計算在這種意義上，計算複雜性理論比可計算性理論更與實際的計算有關。但我們應當指出，在計算複雜性理論這一領域中，也存在著是否與實際計算有關的問題。
我們首先陳述斯坦福大學的丹奇希不久前獲得的一項研究成果。我們回憶稱之為1979年數學方麵的衛星的故事（見習）。一位青年蘇聯數學家哈赤揚在1979年發表了一種解線性規劃問題的巧妙的算法，這個算法已被證明是一種多項式算法。到目前為止，日常計算中解線性規劃問題的算法是丹奇希提出的單純形法，這個算法已被證明是指數算法。由此看來，似乎可以預測哈赤揚的算法是勝過丹奇希的了。
令人驚異的是丹奇希通過一個例子（這個例子包含有一千個不等式和三千個未知數）證明了：這個問題如果應用單純形法（在這是一種每秒能執行三百萬條指令的計算機）上需要三十分鍾的時間，而應用哈赤揚算法來解這個問題時，估計要用五千萬年。
丹奇希根據這一試驗得出下列結論，說一個問題是多項式時間內的可解的，實際上是幾乎沒有說什麼。
對上麵這一現象的解釋在於下列的事實，在計算複雜性理論中，通常我們是考慮最壞情形的複雜性，而不是平均情形的複雜性。最近已經發現，哈赤揚算法的最壞情形複雜性是，而單純形法的複雜性是指數的，但就平均複雜性而言，單純形法的複雜性僅僅是。哈赤揚算法和單純形法二者的效率的比較清楚地說明了，就與實際計算有關這一點而言，應該采用平均情形的複雜性而不采用最壞情形的複雜性。所以，概率算法可能是與實際計算有關的。
在過去大約五年中，有幾位傑出的計算複雜性理論的學者已開始注意概率算法，在1979年關於算法與複雜性理論的新方向與新成果的討論會上，對於概率算法這一方麵做了概述。在這一方麵上我們假定這些問題的實例是來自特定的概率分布，並指出某些多項式時間算法幾乎一定可以導致接近於最優的答案。為概率算法提出了另一種方向和方法，他並不假定待解決問題的實例的分布情形，他將隨機的概念引入算法本身之中。這種隨機化導致有效率。他提出了一種可以判定數是否是素數的概率算法-這一算法中包含有，對十任意給定的和如果則這個算法可以給出其概率的止確答案。
在幾個基本假定之上的。直先是下列的基本假定（以下我們將稱這些假定為“論題”）：一個函數就計算而言是可行的（也就是實際可計算的）當且僅當它是多項式可計算的(即多項式時間內可計算的。這一論題是在60年代中期提出的，以下我們將稱之為“可行性論題”。）
其次，有和其他人提出的論題，這個論題是說：一切合理的計算模型都是大致等價的（也就是說，相對於多項式複雜性而言是等價的，以下我們將稱之為“大致等價性論題”）。