Lesson 5

If you solve a Sudoku puzzle and want to demonstrate it to your friends, you simply show them the solution, and they can easily verify that it is indeed a solution. But what if there is no solution to the puzzle? What can you give your friends as a certificate of the absence of such a solution? Are there short proofs of the non-isomorphism of two graphs? This is also an open question. The class of such problems (whose complements lie in NP) is denoted by co-NP. In other words, co-NP is the class of languages for which there are short proofs of non-membership.

We do not know whether the classes NP and co-NP coincide. It can be shown that if P\(=\)NP, then NP\(=\)co-NP (and the entire polynomial hierarchy collapses to the first level).