4
$\begingroup$

A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will generally be an intractable number of possibilities. How can it be possible to deterministically verify the no answer for all possibilities in polynomial time?

As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Don't conflate the number of possible solutions to check with inherent hardness. There are $n!$ solutions to sorting $n$ items; however we can easily solve that without having to brute force them all. $\endgroup$ – Nicholas Mancuso Nov 25 '15 at 19:38
7
$\begingroup$

This kind of argument presupposes that the only way to (for example) prove that a SUBSET-SUM instance is not solvable is by going over all subsets and checking that their sum doesn't match. This isn't true — a meet-in-the-middle algorithm works in time $O(\sqrt{2}^n)$ rather than $O(2^n)$, where $n$ is the number of sets.

Furthermore, consider the analog of this question for polynomial space rather than time. In this case it does hold that NPSPACE=coNPSPACE, for the simple reason that PSPACE=NPSPACE.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Ok, but that still looks supra-polynomial to me. Is there a well-known polynomial time verifier for any other coNP-complete problem? I would also like to give a better example. Should I just add it to the original question? $\endgroup$ – slkpg Nov 26 '15 at 14:06
  • $\begingroup$ It's conjectured that NP$\neq$coNP. $\endgroup$ – Yuval Filmus Nov 26 '15 at 14:12
-2
$\begingroup$

If I'm understanding your question correctly, then I see no problem with the ability to verify a "no" answer in polynomial time. I think you misunderstand what the complement is calling for.

Given the subset-sum problem, an answer would be a subset of the given set, and to verify that answer would be to determine whether or not its sum equals the target sum. So for a "no" answer, simply add all values in the answer (in exactly the same way you're adding the values of a "yes" answer) to arrive at the conclusion that the sum of the subset does not equal the target sum for the specified problem.

You say:

The complement is that the no answer must be similarly verifiable.

This is still true. You don't have to be able to verify all possible "no" answers, together, in polynomial time to satisfy the complement. You only have to be able to verify a given "no" answer in polynomial time. Which holds.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I don't think you understand what "no certificate" is. It is not determining if a putative solution is invalid. It requires showing that a problem instance has no possible solution. $\endgroup$ – Nicholas Mancuso Nov 26 '15 at 0:22
  • $\begingroup$ I understand it quite well, but maybe I don't understand the question. The complement (co-NP) for the subset sum problem asks whether or not, "for a given set of integers, every subset of integers must have a non-zero sum" which, as a problem, is not seen to be in the set of NP. This seems obvious. However, a 'no' answer to that complement could easily be verified in polynomial time. $\endgroup$ – s.burns Nov 26 '15 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.