Logic for why NP is not closed under complement?
Moderators: phlip, Moderators General, Prelates

 Posts: 1
 Joined: Thu Apr 20, 2017 3:16 pm UTC
Logic for why NP is not closed under complement?
I don't see why we can't use the same logic used to prove that P is closed under complement. Would someone mind breaking it down for me?
 phlip
 Restorer of Worlds
 Posts: 7543
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Logic for why NP is not closed under complement?
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:
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 nondeterministic 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).
which sums it up pretty succinctly.Wikipedia wrote: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.
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 nondeterministic 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).
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Logic for why NP is not closed under complement?
Well said.
I want to add another way to describe the first way of looking at the nondeterministic Turing machine (NTM) explanation:
It's the thereexists/forall difference that means they're probably not equivalent. With a deterministic TM, there is no difference between thereexists/forall because there is always exactly one path.
(Consider, of course, trying to negate M. "yes <=> ∃p. p accepts", so if we negate that to go from NP to coNP, we get something like "no <=> ¬∃p. p accepts", aka "no <=> ∀p. p rejects". Same thereexists/forall deal.)
I want to add another way to describe the first way of looking at the nondeterministic Turing machine (NTM) explanation:
 A problem is in NP => there is some NTM M that can answer it in polytime
 M returns a "yes" if there exists a path through M, given the input, that accepts
 M returns a "no" if for all paths p through M, given the input, p rejects
It's the thereexists/forall difference that means they're probably not equivalent. With a deterministic TM, there is no difference between thereexists/forall because there is always exactly one path.
(Consider, of course, trying to negate M. "yes <=> ∃p. p accepts", so if we negate that to go from NP to coNP, we get something like "no <=> ¬∃p. p accepts", aka "no <=> ∀p. p rejects". Same thereexists/forall deal.)
Who is online
Users browsing this forum: No registered users and 8 guests