OK, so it's been a while since I've dabbled in complexity theory so I'm a bit rusty, and I hit up Wikipedia for a quick refresher, and it helpfully says:
Every deterministic complexity class is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.
which sums it up pretty succinctly.
However, there are two definitions of NP that get thrown around... they're ultimately equivalent, but they sorta approach it from different angles. That short quote works for one of the definitions, but the other definition is more common and it can be harder to see how it applies.
One definition is that they're problems where, if you have a candidate solution, you can verify
the solution in polynomial time (but you aren't necessarily able to find
a solution in polynomial time). The other definition is problems that can be solved in polynomial time by a non-deterministic Turing machine (which is where the abbreviation "NP" comes from)... a nondeterministic machine being one where the program could go in multiple directions at any given point, and as long as any
path through the program accepts, then the program as a whole accepts.
You can think of these as equivalent by making the "solution" that you're verifying into the path through the nondeterministic machine that accepts... you can verify whether any given path accepts in polynomial time by a normal deterministic machine, while a nondeterministic machine can essentially test them all at once and pick the one that accepts.
So, to come back to the coNP question... for the "verifier" definition, consider that our definition is that every question where the answer is "yes" has a solution that can be verified in polynomial time... but we don't say anothing about the ones where the answer is "no"
. They may or may not have quickly verifiable solutions.
Consider the classic examples of NP problems - logic puzzles. Take, for instance, a sudoku board, with a handful of givens but mostly not filled out, and the question "is this puzzle solveable?"... well, if the answer is "yes", there should be a solution to the board, which you can check very quickly (make sure it matches all the givens, and satisfies the rules of the game, with no duplicate numbers etc). But if the answer is "no", there isn't necessarily any simple thing you can write down that can be quickly verified to confirm that you're correct, this sudoku board is unsolveable. Certainly, just given a block of code that verifies sudoku solutions, you couldn't easily turn that into a verifier for candidate proofs that a sudoku board can't be solved.Finally, a minor nitpick that we don't know for sure that NP isn't closed under complement, whether it is or not is still an open question (though mathematicians generally expect it isn't).