Cobham-Edmonds 論題（Cobham-Edmonds thesis）
/ COB-um / ED-mundz /
普通的 Church-Turing 論題是關於「究竟什麼是可計算」的主張：任何合理機器能算的，圖靈機也能算。Cobham-Edmonds 論題是同一個想法被磨利，用來問成本，而不只是可能性。它實際上是說：「可有效計算」的正確形式化替身是「可在多項式時間內計算」，而這個概念在所有合理的確定型計算模型間都相同。它是從日常用語「高效」通往精確類別 P 的橋樑。
這個論題立足於一個具體事實，而非單純的哲學：合理的確定型模型彼此只以多項式額外開銷互相模擬。多帶圖靈機可被單帶圖靈機模擬，時間至多以平方放大；隨機存取機，或你最愛的程式語言，可被圖靈機以多項式減速模擬，反之亦然。因為多項式的多項式仍是多項式，「在多項式時間內執行」能挺過這些翻譯中的任何一個。所以若一個問題在某個合理模型上屬於 P，它在所有模型上都屬於 P；當你更換硬體時，P 的界線不會移動。正是這種穩健性，使 P（而非像「線性時間」那樣較窄的界限）成為可解的自然定義。
兩則警告讓這個論題保持誠實。它是論題，不是定理：和 Church-Turing 論題一樣它無法被證明，因為「合理模型」是個非正式的概念，儘管至今每個被造出來的合理模型都遵守它。而量子電腦是那個著名的活生生問號。它們似乎違反了強（確定型）形式，因為它們能在多項式時間內分解整數，而沒有已知的古典對應；它們是否違反更廣的擴展 Church-Turing 論題則是未決問題。不過對古典確定型計算而言，Cobham-Edmonds 是 P 與模型無關的基石原因。
把一個寫成虛擬碼（RAM 風格模型）的乾淨演算法轉成單帶圖靈機。每個高階步驟至多花費多項式數目的紙帶步數，所以一個 O(n^3) 的虛擬碼方法變成某個 O(n^c) 的圖靈機。屬於 P 的身分被保留下來，這就是我們能自由地用任何方便的模型來推理 P 的原因。
合理模型彼此以多項式額外開銷互相模擬，所以 P 在它們之中全都相同。
它是論題，不是可證明的定理（其中的「合理模型」是非正式的）。量子電腦可能打破確定型形式（例如快速分解），但沒有任何模型打破支撐 P 穩健性的古典主張。