co-NP 與 P 對 NP 問題（co-NP and P-versus-NP）
/ co-NP = koh-en-pee /
NP 內建一份不對稱：它對「是」答案承諾一個簡短、可檢查的證明，卻對「否」答案隻字未提。co-NP 是它的鏡像——那些「否」答案有簡短、可檢查證明的問題所成的類別。若 SAT（「這個公式可滿足嗎？」）因為一組可滿足指派見證了「是」而屬於 NP，那麼它的補問題 UNSAT（「這個公式不可滿足嗎？」）就屬於 co-NP：UNSAT 的「否」（亦即它「確實」可滿足）可由一組指派見證，但它的「是」（真正不可滿足）卻似乎根本沒有簡短憑證。這種「不可滿足性的證明」是否必然冗長，是最重大的未解問題之一。
精確地說，一個問題屬於 co-NP，若它的「補問題」（交換是與否）屬於 NP。等價地，co-NP 問題對「否」實例有一個多項式時間驗證器：每個「否」都附帶一個驗證器會檢查的簡短憑證。P 同時坐落於 NP 「與」co-NP 之內，因為若你能在多項式時間內「解出」一個問題，你就能為任一答案出證（重跑演算法即可），所以答案不需要另外的證明。著名的 P 對 NP 問題問的是 P 是否等於 NP：每個「是」答案能被快速「檢查」的問題，是否也能被快速「解出」？等價地說，非決定性那一份好運的猜測，是否總能被誠實的決定性工作以僅多項式的額外代價取代？任一方向的證明都將是劃時代的：P = NP 將意味著 SAT、蛋白質摺疊與上千個最佳化問題全變得可解（而大多數現代密碼學將崩潰）；P 不等於 NP 則將證實「某些問題本質上難搜尋」的直覺。它是七個千禧年大獎問題之一，懸賞百萬美元，而儘管數十年的努力，它依然全然未解。
三個誠實的澄清。第一，幾乎所有人都「猜想」P 不等於 NP，但那是信念而非定理——每個建立在其上的主張（包括「NP 完全意味著沒有有效演算法」）都帶著這個但書。第二，有個相關的猜想是 NP 不等於 co-NP；若兩者相等，不可滿足性就會有簡短證明，而專家對此存疑。若 NP = co-NP 不成立，則 P 不等於 NP 隨之成立，但反之不然，所以這些是層層相疊的未解問題。第三，一個微妙的結構事實（Ladner 定理）：「若」P 不等於 NP，那麼 NP 並非乾淨地只切成「容易的 P」與「最難的 NP 完全」兩塊——必然還存在 NP 中間問題，屬於 NP 卻既不在 P 中、也不是 NP 完全。所以在猜想之下，這片地景比兩分法更豐富，質因數分解與圖同構等候選被疑為住在那塊中間地帶。
恆真式檢查是經典的 co-NP 問題：「這個布林公式在『每一種』指派下都為真嗎？」。一個「否」有簡短憑證——一組使它為假的指派，瞬間可檢查。但一個「是」（它確實是恆真式）似乎需要你排除所有 2^n 種指派，沒有顯然的簡短證明。這份不對稱正是為什麼 TAUTOLOGY 屬於 co-NP、且被猜想不屬於 NP。
co-NP：「否」答案有簡短證明。P 在 NP 與 co-NP 之內；P=?NP 與 NP=?co-NP 仍未解。
P 不等於 NP 是個「猜想」，不是已證事實——「NP 完全」形式上意指「除非 P = NP，否則無多項式演算法」。此外 NP 與 co-NP 被猜想相異；若兩者相等，不可滿足性就會有簡短證明，那將令人震驚。