debugMinor
Seems like NP cannot equal coNP by the definition of NP
Viewed 0 times
cannotconpdefinitiontheequallikeseems
Problem
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?
As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?
Solution
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.
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.
Context
StackExchange Computer Science Q#49961, answer score: 7
Revisions (0)
No revisions yet.