Why do complexity theorists expect NP and co-NP to be different classes?
answer
- think about proof length, not run time
- short refutations for every tautology
- lower bounds only for the weaker systems
- equality collapses the quantifier tower
- space behaved differently from time
basics
~20 sEquality would mean every tautology has a short, checkable proof — a uniformly short refutation for every unsatisfiable formula. Decades of work on proof length have produced no such system, and superpolynomial lower bounds are theorems for the weaker systems analysed so far.
solid answer
~50 sRestate the question as one about proof length. NP equals co-NP exactly when some propositional proof system proves **every** tautology with a proof polynomial in the formula's size. That reframing is what the evidence is measured against, and the evidence points one way: for the weaker proof systems that have been analysed, superpolynomially long proofs are *provably* required on natural formula families — the pigeonhole formulas are the classic example for resolution. For the strongest systems nothing is proved either way, which is why the question stays open rather than closed. Experience supports the intuition too: finding a solution and proving none exists behave differently in practice. But intuition is not proof, and there is a cautionary precedent — for nondeterministic **space**, the analogous complement question was settled the other way, with the classes turning out to be closed under complement.
go deeper
Recall that both questions are open and that neither class is known to contain the other. Do not present either separation as settled mathematics.
Explain the reformulation: equality of the two classes is the statement that every tautology has a proof whose length is polynomial in the formula.
State the evidence with its limits — lower bounds are theorems for the weaker proof systems and unproved for the strongest — and keep the one-way implication with P versus NP straight.
Use it to calibrate promises: a system may be asked to demonstrate impossibility, and no advance in tooling is owed to you by an open problem. Design so the verdict you depend on is the demonstrable one.
## What the two classes assert **NP** is the class of problems whose *yes* instances carry a short certificate that a polynomial-time verifier checks. **co-NP** is its mirror: the class of problems whose *no* instances carry one, equivalently the class of problems whose complement is in NP. Asking whether the two are equal is asking whether the ability to demonstrate a positive answer always comes with an ability to demonstrate the negative one. Everything solvable in polynomial time lies in both, and no containment either way between the full classes is known. So there are three live positions: they are equal, NP is not contained in co-NP, or co-NP is not contained in NP — and the second and third are the same statement by complementation. ## Restating the question as proof length The productive reformulation drops the class vocabulary entirely: - Tautology is co-NP-complete, so the whole question turns on it: is tautology in NP? - A certificate that a formula is a tautology is exactly a **proof** of it in some system a checker can replay in polynomial time. - So NP equals co-NP precisely when there exists a propositional proof system in which every tautology has a proof of size polynomial in the formula. That is a concrete, mathematical target, and it converts a question about machines into a question about how long proofs have to be. ## The evidence, stated with its limits This is where care is required, because the honest picture is partial: - For several **weaker** proof systems, superpolynomial lower bounds are theorems. Resolution needs exponentially long refutations for the pigeonhole formulas, which encode a counting fact that resolution cannot express compactly. - For the **strongest** systems studied, nobody has proved any superpolynomial lower bound at all. The absence is not evidence of shortness; it is an absence of results. - No proposed system has been shown to give short proofs of every tautology, and many have been shown not to. - The working intuition from practice — that searching for an object and proving no object exists feel different — is suggestive and is not an argument. So the expectation of a separation rests on a pattern of lower bounds in the cases where anyone has managed to prove anything, plus the failure of every attempt at the opposite. That is a belief, held for good reasons, not a theorem. ## What equality would and would not buy | Statement | Status | Follows from NP = co-NP? | |---|---|---| | Every unsatisfiable formula has a polynomial-size refutation | equivalent to it | yes, by definition | | The tower of classes built above NP by alternating quantifiers collapses to its first level | known consequence | yes | | Satisfiability is solvable in polynomial time | the P versus NP question | no | | Hard search problems become fast in practice | separate question | no | The third row is the one candidates most often get wrong. A short proof existing does not mean a short proof is easy to **find**; certificates describe verification, not search. Equality of NP and co-NP would be a mathematical earthquake and would still leave the tractability question untouched. The implication runs one way between the two open questions. P is closed under complement, so if P equalled NP then NP would equal co-NP. Contrapositively, proving NP different from co-NP would immediately prove P different from NP. That makes the separation of NP and co-NP the **stronger** claim, and it is part of why nobody expects it to fall first. ## The cautionary precedent The intuition 'nondeterminism cannot be complemented for free' sounds compelling and is known to be **wrong in a neighbouring setting**. For nondeterministic computation measured by memory rather than time, the analogous complement question was settled — and the answer was that the classes *are* closed under complement, by an argument that counts reachable configurations rather than guessing a witness. The moral is not that NP equals co-NP. It is that the appealing asymmetry argument is not self-evidently right, and the reason the question is still open is that every attempt to make it rigorous has failed. For an engineer the practical residue is modest and real: treat 'there is no solution' as a fundamentally more expensive claim to justify than 'here is one', design systems so the demonstrable verdict is the one you rely on, and do not promise that a tool will always be able to prove impossibility quickly.
- Would proving NP different from co-NP settle P versus NP?Yes. P is closed under complement, so P equalling NP would force NP to equal co-NP; the contrapositive gives P different from NP. The converse is not known — P could differ from NP while NP still equalled co-NP, as far as anyone can prove.
- If NP equalled co-NP, would hard problems become tractable?No. Every unsatisfiable formula would have a short refutation, but nothing says that refutation could be found quickly. Certificates concern verification; tractability is the separate P versus NP question, which would remain open. The practical world could look exactly the same the day after.
saying these in an interview costs you the question
- Says NP and co-NP have already been proved different.
- Claims NP equalling co-NP would make hard search problems fast.
- Treats P versus NP and NP versus co-NP as the same statement.
- Believes no nondeterministic class can ever be closed under complement.
- Takes the absence of short refutations found so far as proof that none exist.