P 的模型無關性（model-independence of P）
一個定義的用處取決於它有多穩定。如果「可在多項式時間內解出」對圖靈機是一回事、對真實電腦又是另一回事，那麼 P 就只是學術上的奇珍，而非對世界有意義的主張。P 的模型無關性是這件令人欣慰的事實：一個問題是否屬於 P，不取決於你用哪個合理的確定型計算模型來定義它。無論你怎麼接線組裝電腦，P 都是同一個類別。
原因正是 Cobham-Edmonds 論題裡已遇過的多項式額外開銷模擬。從單帶圖靈機換成多帶機，你可能省時間，但換回去至多花一次平方。換到隨機存取機、或換到普通程式碼，雙向的翻譯都只花一個多項式因子。現在把這些疊起來：一個多項式執行時間，跑過一個多項式額外開銷的模擬器，仍是多項式，因為多項式的多項式是多項式。所以一個在某模型上有 n^3 演算法的問題，在任何其他模型上會得到某個 n^c 演算法，屬於 P 的身分被保留。（較細的區分並非模型無關，這正是我們對所有多項式取聯集的原因：TIME(n^2) 這個類別可能在模型間移動，但 P 不會。）
正是這種穩健性，許可了複雜度理論的整套做法：我們在任何喜歡的乾淨模型裡展示一個多項式時間演算法來證明某問題屬於 P，確信這個判決會轉移過去。這也是為什麼 P（而非較窄的界限）是可解的標準意義。那個著名的可能例外落在古典確定性之外：量子計算（BQP）並不知道能否被古典機器以僅多項式額外開銷模擬，所以模型無關性是針對合理的古典確定型模型的陳述，而量子問題則被分開保留為未決。
排序在隨機存取機上是 O(n log n)。把那台機器在單帶圖靈機上模擬，執行時間會升到某個多項式，也許 O(n^2) 或 O(n^3)，但它仍是多項式。所以「排序屬於 P」在每個合理模型上都成立，即使確切的指數取決於模型。
確切的指數在模型間移動，但屬於 P 的身分不變。
模型無關性對 P（對所有多項式取的聯集）成立，但對像 TIME(n^2) 這樣的單一界限不成立，後者可能因模型而異。這個古典保證對量子機器隻字未提，後者並不知能否被多項式模擬。