NP 的非確定型機器定義（nondeterministic-machine definition of NP）
定義 NP 還有第二種等價方式，而它正是字母 N 的來源。想像你站在迷宮口，與其小心走，你在每個岔路口神奇地複製自己，於是所有路徑同時被探索；只要「任何一個」分身抵達出口，就算解開了。這正是你在 NFA 那裡遇過的非確定性——機器能同時處於數個狀態。NP 就是讓一台非確定型機器執行、但只准跑多項式時間時，所得到的東西。
形式上，一個問題屬於 NP，是指存在一台非確定型圖靈機能在多項式時間內判定它。這種機器分兩階段運作，可讀成「先猜再查」。在「猜」階段，它非確定地寫下一段字串，概念上平行嘗試每種可能字串；這段猜出的字串正是證書。在「查」階段，它確定型地執行以驗證猜測，耗時多項式。若「存在」某個猜測導致接受，機器就接受該輸入。「存在一條接受路徑」與驗證器定義中的「存在一份證書」是同一回事，這正是兩個定義描述完全相同類別的原因。
在兩種觀點間互譯既機械又值得內化。一個驗證器加上一段猜出的證書就是一台非確定型機器；一台非確定型機器那串幸運的選擇就是一份證書。「猜」是數學虛構，不是真實硬體，與 NFA 完全一樣：我們並非主張電腦能神奇地自我複製，它只是定義「存在一份短證書」的乾淨方式。賭注只是比有限自動機高得多。對 NFA，非確定性在能力上毫無代價；在這裡，非確定型多項式時間是否真的比確定型多項式時間更強，恰恰就是懸而未決的 P 對 NP 問題。
一台用於 3-SAT 的非確定型機器這樣運作：在一次非確定的爆發中，它為每個變數猜一個真值（一份證書），然後確定型地掃過每個子句，確認每個都被滿足。公式可滿足，恰恰是當「某條」猜測分支導致接受時，這正對應「存在一個滿足賦值」。
非確定地猜一份證書，再確定型地在多項式時間內驗證它；一條接受路徑就是一份證書。
非確定的「猜測」與 NFA 中的裝置是同一個，且純屬概念性，既非隨機也非真實的平行硬體。它只模擬「存在一份證書」，僅此而已。