證書（certificate）

證書就是夾在課本最後面的解答頁。眼前的問題也許是場殘酷的搜尋，但證書是那張短箋，寫著「答案在此，而它為何成立也在此」。你不必去找它，但有了它你片刻間就能確認結果。在複雜度理論裡，證書就是那份能把困難搜尋變成快速檢查的旁證資訊。

具體地說，證書是與輸入 x 一起遞給驗證器的額外字串 c。它是「x 的答案為是」這件事所提出的證據。對 NP 而言，定義性的要求是證書必須「短」：其長度必須以 x 長度的多項式為界，這樣驗證器才能在它的多項式時間預算內讀完。理解證書的好方法是把它想成「若懷疑者要你證明某個是答案，你會指向的那個東西」。對「這張圖可三著色嗎？」，證書是頂點實際的一種三色著色。對「這道數獨有解嗎？」，它是一張填滿的格盤。

證書只對「是」實例存在，而且只需要其中一個有效。NP 的定義說「存在」一份驗證器會接受的證書；若答案為「否」，則每個候選證書都會失敗。這種不對稱正是 NP 與其補集 co-NP 可能不同的全部原因。這也是為何證書作為設計工具如此好用。要證明一個問題屬於 NP，你就決定「是」長什麼樣、論證證據總能被簡短地寫下，並確認某個檢查器能快速驗證它。注意：證書認證的是答案，它不必透露答案是怎麼找到的。