憑證與驗證器（certificate and verifier）
想像一場數學考試，難的是「找出」證明，而「檢查」別人寫好的證明相對容易。那個證明就是「憑證」——一小段「答案為是」的證據——而讀它並判定「有效」或「無效」的閱卷者就是「驗證器」。這一對，用樸素的機械語言，捕捉了「一個問題屬於 NP」的意義：「是」的實例必須附帶可檢查的證據，而檢查者必須夠快。
形式上，某問題的驗證器是一個決定性演算法 V(x, c)，吃進問題輸入 x 與候選憑證 c，輸出接受或拒絕。我們要求兩件事。完備性：若 x 是「是」的實例，則「存在」一個憑證 c（長度為 |x| 的多項式）使 V(x, c)＝接受。健全性：若 x 是「否」的實例，則對「每一個」c 都有 V(x, c)＝拒絕。而且 V 必須在 |x| 的多項式時間內執行。憑證是把累人的搜尋變成快速檢查的「答案卡」；驗證器是不會被假卡騙倒的可信閱卷者。一個問題屬於 NP，恰好就是當這樣的多項式時間驗證器存在時。具體來說，對圖的 3 著色，憑證是每個頂點的一個顏色；驗證器掃過每條邊，只有當兩端點顏色不同時才接受——顯然是多項式，而且當不存在合法著色時無論如何都無法被滿足。
兩個微妙處很重要。第一，憑證必須「簡短」（多項式長度）——若允許指數長的提示，你就能把整個暴力搜尋偷渡進去，這個概念便毫無意義。第二，那份不對稱：NP 保證「是」答案有可檢查的證據，而非「否」答案。並沒有要求「這張圖『不可』3 著色」要有簡短憑證；「否」答案是否總有簡短證明，正是 co-NP 的未解問題。憑證／驗證器這幅圖像是通往 NP 與歸約最直觀的門，因為證明「屬於 NP」通常就只是描述出憑證與檢查者而已。
漢米頓迴路：「這張圖有一條恰好造訪每個頂點一次的迴路嗎？」。憑證：提議的頂點順序 v1, v2, ..., vn, v1。驗證器：檢查每對相鄰頂點之間有邊，且全部 n 個頂點各出現一次——O(n) 的工作。若圖確實有這樣的迴路，此憑證便存在；若沒有，任何順序都過不了關。
憑證＝「是」的簡短證據；驗證器＝快速檢查者，任何假證據都騙不過它。
驗證器必須「健全」：在「否」的實例上，不得有任何憑證矇混過關。一個會接受某些假證明的檢查者，無法證明問題屬於 NP。而且「屬於 NP」對「否」實例是否有簡短證明隻字未提——那是 co-NP 的另一個問題。