HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Seems like NP cannot equal coNP by the definition of NP

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#49961, answer score: 7

Revisions (0)

No revisions yet.