Questions: Co-NP and Complementary Complexity Classes

Question 1

A researcher announces they have found a polynomial-length proof that a specific 10,000-variable Boolean formula has no satisfying assignment, and that this proof can be verified in polynomial time. What is the most significant complexity-theoretic implication?

• A. This would prove P = NP, because it shows that an NP-complete problem (SAT) can be solved efficiently
• B. This would show that UNSAT ∈ NP, which would imply NP = co-NP
• C. This would have no major implications, because verifying a specific proof is not the same as solving the general decision problem
• D. This would show that co-NP ⊂ NP, making co-NP a proper subset of NP

Answer: (B)

UNSAT is co-NP-complete. If there were a polynomial-length certificate proving unsatisfiability (verifiable in polynomial time), UNSAT would be in NP — since NP is exactly the class of problems where 'yes' instances have such certificates, and 'yes to UNSAT' means 'the formula has no satisfying assignment.' Because UNSAT is co-NP-complete, placing it in NP would mean every co-NP problem is in NP, so NP = co-NP. This would be a major result — we believe NP ≠ co-NP — but it would NOT prove P = NP. NP = co-NP is a weaker statement than P = NP.

Question 2

Which of the following correctly characterizes the relationship between P, NP, and co-NP?

• A. If NP = co-NP, then P = NP, since collapsing the certificate hierarchy implies efficient solving
• B. P ⊆ NP ∩ co-NP; P = NP implies NP = co-NP, but NP = co-NP does not imply P = NP
• C. co-NP is a proper subset of NP because every 'no' certificate can be reframed as a 'yes' certificate via negation
• D. NP and co-NP are disjoint: no problem can simultaneously have short 'yes' and 'no' certificates

Answer: (B)

P is closed under complementation: if L ∈ P, then its complement L̄ ∈ P (just flip accept/reject). This means P ⊆ NP ∩ co-NP. If P = NP, then NP = P = co-NP, so NP = co-NP follows. But the converse fails: NP = co-NP says both 'yes' and 'no' instances have short certificates, but says nothing about efficiently FINDING solutions — which is what P = NP would require. PRIMES is in NP ∩ co-NP (both primality and compositeness have short certificates) yet was not known to be in P for decades, illustrating the real gap between having certificates and having efficient algorithms.

Question 3

If a problem L is in NP ∩ co-NP — meaning both 'yes' and 'no' instances have polynomial-size certificates verifiable in polynomial time — then L should also be in P.

• T. True
• F. False

Answer: False

NP ∩ co-NP contains problems believed to be outside P. PRIMES (is n prime?) is in NP ∩ co-NP: a Pratt certificate proves primality, and a factorization proves compositeness — both verifiable efficiently. Yet PRIMES was long thought to likely be outside P, and the AKS algorithm (2002) proving PRIMES ∈ P was a celebrated result precisely because this was not obvious. Having certificates for both answer types does not provide an efficient decision procedure; we believe P ⊊ NP ∩ co-NP ⊊ NP.

Question 4

UNSAT — determining whether a Boolean formula has no satisfying assignment — is in co-NP because the complement of UNSAT is SAT, which is in NP.

• T. True
• F. False

Answer: True

This follows directly from the definition of co-NP: a language L is in co-NP if and only if its complement L̄ is in NP. The complement of UNSAT is SAT (satisfiable formulas), and SAT is in NP because a satisfying assignment is a polynomial-size certificate verifiable in polynomial time. Therefore UNSAT ∈ co-NP. Equivalently: UNSAT has efficient 'no' certificates (a satisfying assignment proves a formula is NOT unsatisfiable), while a 'yes' certificate (proving no assignment works) requires reasoning over all 2ⁿ possible assignments — no short certificate is known.

Question 5

SAT is in NP because a satisfying assignment serves as a short, efficiently verifiable 'yes' certificate. Explain why UNSAT seems unlikely to also be in NP — that is, why a polynomial-size 'yes' certificate for UNSAT appears fundamentally harder to construct.

Model answer: For SAT, a 'yes' certificate is a single assignment of n Boolean variables — n bits long, trivially verifiable by plugging into the formula. For UNSAT, a 'yes' certificate would need to prove that ALL 2ⁿ possible assignments fail to satisfy the formula. There is no known short way to compress this fact. Unlike a single counterexample (which suffices to prove SAT), a proof of universal non-existence over exponentially many cases seems to require reasoning about the entire search space — and we know of no way to do this with polynomial-size objects for arbitrary formulas. This asymmetry between existential and universal proofs is why NP and co-NP are believed to differ.

The key intuition is the asymmetry between ∃ and ∀. SAT asks '∃ assignment satisfying φ?' — existence is certifiable with a single witness. UNSAT asks '∀ assignments, φ evaluates to false?' — universal statements resist short certification because you cannot exhibit one counterexample; you must rule out all possibilities. If UNSAT were in NP, there would be polynomial-length 'yes' certificates for every unsatisfiable formula. For formulas with millions of clauses and thousands of variables, compressing a proof of non-satisfiability into polynomial size would require deep structural insight about why no assignment works — something our current proof systems cannot achieve efficiently for arbitrary formulas. Whether NP = co-NP remains open, but most complexity theorists believe the asymmetry is real and fundamental.