Skip to interview prep
Apexed

400. What is co-NP? Explain using tautology checking.

HardComplexity classes

Technical
Show model answer

co-NP contains problems whose complements are in NP: every 'no' instance has a short, checkable certificate. TAUTOLOGY (is this formula true under every assignment?) is in co-NP because a falsifying assignment proves the answer is no. It is co-NP-complete, since a formula F is a tautology exactly when ¬F is unsatisfiable.

No short certificate for 'yes, this is a tautology' is known, so TAUTOLOGY is believed not to be in NP. If NP ≠ co-NP, then P ≠ NP, because P is closed under complement. P ⊆ NP ∩ co-NP, and problems such as integer factoring (as a decision problem) sit in NP ∩ co-NP without known polynomial algorithms, which is evidence that factoring is not NP-complete.

What is co-NP? Explain using tautology checking. — Data structures & algorithms interview question — Apexed