本節書摘來自華章計算機《計算複雜性：現代方法》一書中的第1章，第1.6節，作者 ［美］桑傑夫·阿羅拉（sanjeev arora），博阿茲·巴拉克（boaz barak），譯 駱吉洲，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
我們用圖靈機定義“可計算”語言的各種複雜性類及類p。如果選用其他計算模型，這些類會有差別嗎？在發現了計算但采用其他模型而不是圖靈機作為計算模型的高等外星人眼裡，這些類會有差別嗎？
我們已經遇到圖靈機模型的各種變形，用其中最弱的模型來模拟最強的模型将導緻運作時間平方增加。是以，作為可計算問題的集合，多項式時間在這些變形上是一樣的。
在圖靈和邱奇的工作發表之後的最初幾十年中，很多其他的計算模型被發現，其中有些模型十分怪異。當時人們很容易地就證明了圖靈機能夠模拟其他計算模型，模拟過程至多使得運作時間多項式地變高。是以，在這些模型上類似地定義的類p不會比圖靈機定義的p更大。
絕大多數科學家均相信邱奇圖靈(ct)命題,它斷言任何可被實體實作的計算裝置均可以被圖靈機模拟，不管這種裝置是基于晶片、dna、中子的還是基于外星人技術的。這就是說，任何其他模型上的可計算問題的集合不會比圖靈機上可計算問題的集合更大。（ct命題不是定理，正如我們目前的了解，它僅僅是對世界的本質的一種信念。）
現在，我們給出關于類p的定義的一些争議和解決這些争議的過程中出現的以下相關複雜性類。
最壞情況精确計算過于嚴格。類p的定義考慮的僅僅是在所有可能的輸入上計算函數的算法。一個争議之處是，所有輸入并不都出現在實際場合中，而算法隻需對實際場合下出現的輸入上有效即可。平均複雜性部分地解決了這一争議，并由此産生了平均複雜性意義下類似p的複雜性類，參見第18章。我們的觀點是，限定在“實際場合”讨論p僅有純技術意義。
類似地，在遇到像圖的最大獨立集這樣大小的計算函數時，人們通常更願意讨論問題的近似解。第11章和第22章對近似複雜性進行了嚴格處理。
其他可實體實作的模型。前面已經提到了強邱奇圖靈命題,它斷言在任意可實體實作的計算模型上類p不會更大，但其中還有一些微妙之處有待讨論。
(a) 精度問題。圖靈機用離散符号進行計算，但現實生活中某些實體量可以取r中的實數。是以，人們也可以基于能操作實數的某些實體現象來構想執行實數計算的模型。由于存在精度問題，圖靈機隻能近似地模拟實數計算。即便這樣，精度問題也不是圖靈機遇到的本質性障礙（盡管有些研究者不認同這種觀點）。畢竟，由于現實生活中裝置存在噪音，是以實體量的測量隻能精确到有限精度。是以，實體過程不可能涉及任意精度，繼而圖靈機當然可以用有限精度來完成模拟。27即便這樣，我們仍将在第16章中考慮圖靈機的一種修改，使其能夠将實數運算當作基本操作。由此産生的複雜性類跟标準複雜性類之間的聯系十分密切。
(b) 随機性的采用。前面定義的圖靈機是确定型的。如果計算的領域中存在随機性，則人們也可以構想利用随機位源（如投擲硬币）的計算模型。第7章讨論了允許投擲硬币的圖靈機并研究了複雜性類bpp,它是這種計算模型上與p類似的複雜性類。然而，我們在第19章和第20章将會看到，随機型計算模型極可能并不比确定型計算模型更強。
(c) 量子力學的采用。一個更聰明的計算模型使用了量子力學中違背直覺的一些性質。我們在第10章定義了複雜性類bqp,它是類p在量子計算模型中的推廣。我們将看到bqp中的一些問題，目前還不知道它們是否屬于p（盡管目前仍未證明bqp≠p）。然而，量子計算模型是否能被實體實作還是未知的。并且，量子計算機目前似乎也隻能高效地求解為數不多的幾個不屬于p的問題。是以，研究p時獲得的知識仍可能适用于量子計算機。
(d) 其他怪誕實體知識（如弦論）的采用。目前，許多實體理論似乎都得到同樣的複雜性類bqp,盡管許多理論還有待深入了解。
判定問題的限制太強。有些計算問題不易表達成判定問題。事實上，本書将引入幾個複雜性類來處理某些任務的計算複雜性，這些任務包括非布爾函數的計算、搜尋問題的求解、優化問題的近似求解、互動式任務，等等。然而，判定問題的架構已被證明具有強大的表達能力，本書也經常使用這種架構。
我們用埃德蒙茲的引言［edm65］結束本節。埃德蒙茲曾在其著名的論文中給出了求解最大比對問題的多項式時間算法，他在論文中這樣解釋其研究結果的意義：