猜測與驗證（guessing and verifying）

這裡有一個極為好用的方式來解讀 NFA：假裝機器有一個神奇的神諭，在關鍵時刻「猜」出正確的移動——然後接下來的執行只負責「驗證」這個猜測是好的。如果存在一個正確的猜測，就接受；如果沒有任何猜測行得通，就拒絕。這種「先猜再驗」的思維，能把許多糾纏的設計問題化成一行描述。

具體來說，假設你想接受「某處含有 aba 這一段」的字串。你把 NFA 設計成停在一個等待狀態，在每個位置它都可以選擇繼續等待，或是「猜」：「我被許諾的那個 aba 就從這裡開始。」一旦猜了，它就承諾去檢查 a、再 b、再 a；如果這三個符號真的在那裡，它就走到接受狀態。這個猜測不是神奇的預知——它只是可能性之樹上的一條分支，而存在式的接受規則意味著：我們只需要有一條分支讓這個猜測恰好正確就好。

把這個直覺放大，正好就定義了 NP 類：當一個被提出的解（一個猜測，或稱見證／證書）即使很難找到、卻能被「快速驗證」時，這個問題就屬於 NP。對有限自動機而言，猜測總是能廉價地被消除——子集構造法把它整個拿掉。著名的未解問題「P 對 NP」問的正是：對那些更難的問題，這件事是否也成立。所以這個小小的想法，正是計算機科學最重大問題之一的初次嚐鮮。