CMPS130: Overview of complexity classes, Part 3
C. Seshadhri · 9:33
NP and coNP are distinguished by which side of a decision problem has a short, efficiently checkable certificate: SAT is in NP because a satisfying assignment proves a “yes,” while unsatisfiability / tautology and “is...