Logic for why NP is not closed under complement?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

coppacrane
Posts: 1
Joined: Thu Apr 20, 2017 3:16 pm UTC

Logic for why NP is not closed under complement?

Postby coppacrane » Thu Apr 20, 2017 3:21 pm UTC

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?

User avatar
phlip
Restorer of Worlds
Posts: 7535
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Logic for why NP is not closed under complement?

Postby phlip » Fri Apr 21, 2017 10:39 am UTC

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:
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.
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).

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

EvanED
Posts: 4316
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Logic for why NP is not closed under complement?

Postby EvanED » Fri Apr 21, 2017 2:28 pm UTC

Well said.

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 there-exists/for-all difference that means they're probably not equivalent. With a deterministic TM, there is no difference between there-exists/for-all 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 co-NP, we get something like "no <=> ¬∃p. p accepts", aka "no <=> ∀p. p rejects". Same there-exists/for-all deal.)


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 3 guests