非決定性（nondeterminism）
/ non-dee-TER-min-iz-um /
一個普通的（決定性）演算法像照著沒有選擇的食譜走：每一步的下一動作都被決定，所以相同輸入永遠走出相同的單一路徑。非決定性則是一台思想實驗機器，它被允許在某些步驟「分岔」——一次嘗試多種可能，彷彿能分裂成平行的複本，或等價地說，「猜」出正確選擇、稍後才檢查。它不是你買得到的真實機器；它是一個乾淨的數學理想化，讓像 NP 這樣的定義變得俐落。
用兩種等價的方式來想像非決定性機器會有幫助。(1) 猜了再查：一開始它神奇地「寫下」一個憑證 c（那一猜的好運），再對 (x, c) 跑一個完全普通的決定性驗證器。我們說它「接受」x，若「存在」某個猜測導向接受——一個好猜測就夠了，壞猜測直接被忽略。(2) 分岔樹：每當出現選擇，計算就分叉；只要「任一」由根到葉的路徑接受，機器就接受。兩種觀點吻合，因為某條接受路徑上的選擇序列「就是」憑證。關鍵在於：成本是沿「單一」路徑來衡量的：「非決定性多項式時間」意指存在一條多項式長度的接受計算，從不為機器「本可」探索的那指數多條路徑買單。這條不對稱的接受規則——只要某條路徑說是就算是——正好是 NP 定義裡那個存在性的「存在一個憑證」。
為什麼要費神研究一台不可能存在的機器？因為它給了 NP 一個出奇簡單的定義（能被多項式時間非決定性機器解出的問題），而這竟與樸實的驗證器／憑證定義完全等價。它也點明了 P 對 NP 到底在問什麼：「猜」出一個解的能力，是否總能被「只多花多項式倍代價」的決定性工作所取代？兩個誠實的提醒：非決定性「不是」隨機性（隨機機器擲公平硬幣，你在意機率；非決定性機器只要存在單一好運路徑就接受，不附帶任何機率），它也「不是」你蓋得出來的平行性，因為實現所有分支需要指數多個處理器。
非決定性地解 SAT：給定一個含變數 x1..xn 的公式，機器在一個分岔步驟中「猜」出一組真值指派（每個 xi 為真或假），再決定性地求值該公式。它接受，當且僅當「某條」分支使公式為真。那條唯一的接受分支正好就是一組可滿足指派——也就是憑證。猜測藏起了困難的搜尋；只有那便宜的檢查被計時。
只要「任一」分支接受就接受；成本是單一路徑的長度。所走的那條分支就是憑證。
非決定性不是隨機性，也不是蓋得出來的平行性。「只要某條路徑接受就接受」是一個邏輯上的存在量詞，不是擲硬幣；你從不為其餘指數多條路徑付費。那種免費的猜測，正是 P 對 NP 在問「能否捨棄」的那份能力。