驗證器（verifier）

驗證器是複雜度理論裡的機場安檢員。它不必弄清楚你整趟旅程，只要查驗你的登機證與證件，迅速判斷是否相符。給定一個輸入與一份提出的證據，驗證器讀完兩者，給出快速的是非裁決：是，這份證據確實證明答案為「是」；或否，它證明不了。驗證器從不需要自己去發現證據，這正是它工作輕鬆的原因。

精確地說，某問題的驗證器是一個確定型演算法 V，接收兩個參數：原始輸入 x 與一份證書 c。我們說 V 驗證該問題，是指對每個輸入 x，真實答案為「是」當且僅當「存在」一份證書 c 使得 V 接受配對 (x, c)。對 NP 我們再加上資源限制：V 必須在 x 長度的多項式時間內執行完畢，並（因而）只能查看多項式長度的證書。對輸入的多項式限制也限制了有用證書的大小，因為 V 連讀完比自己執行時間更長的證書都做不到。

驗證器觀點是 NP 兩種標準定義中較乾淨的一個，因為它完全不提那種會「猜」的怪機器。它把難度重新框定為關於證據的問題：一個問題屬於 NP，恰恰是當它的「是」答案具有短而能高效檢查的證明。這也是 NP 在實務上如此自然的原因。一個公式的滿足賦值、推銷員的一條合法路線、一張地圖的合法著色，全都是證書，而寫出查驗它的檢查器通常很例行。設計驗證器正是你通常用來「證明」一個問題屬於 NP 的方法。