Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
