co-NP

NP 是這樣一類是非題：答「是」時有一張簡短、容易檢查的證書——一幅難以拼完、但一旦有人把拼好的圖交給你就容易驗證的拼圖。co-NP 是它的鏡像：它是答「否」時有一張簡短、容易檢查證書的類別。如果說 NP 是要產生一個令人信服「答案為是」的見證，co-NP 就是要產生一個令人信服「答案為否」的見證。它們是同一枚驗證硬幣的兩面。

形式上，一個問題屬於 co-NP，恰好當它的補集（把每個是與否對調）屬於 NP。代言者是 TAUTOLOGY（恆真式）：這個布林公式在每種指派下都為真嗎？單一個使它失敗的指派就能證明它「不」是恆真式，所以補集（非恆真式，一種花俏的 SAT）屬於 NP，於是 TAUTOLOGY 屬於 co-NP。等價地說，co-NP 問題是那些能以「對所有」檢查來驗證的問題：「是」意味每個候選都通過，這難以靠舉例確認，卻容易用一個反例反駁。注意 P 同時包含於 NP 與 co-NP，因為確定型多項式演算法對稱地裁決是與否。

co-NP 之所以重要，是作為 NP 的天然夥伴，以及它上方多項式階層的第一階。這裡的大未解問題是 NP 是否等於 co-NP。幾乎所有人都相信「不」：要證明一個公式「沒有」滿足指派，似乎遠難於展示一個奏效的指派。若 NP 真的等於 co-NP，將是撼動全局的結果，而且它本身並不能解決 P 對 NP；不過若 NP 不等於 co-NP，則 P 不等於 NP 隨之成立。針對一個誘人混淆的提醒：co-NP 不是「不在 NP 裡的問題」。許多問題同時坐落在 NP 與 co-NP 中（P 裡的一切都是，而著名的整數分解判定版也是），而這兩個類別是否相等仍屬未知。