snippetMinor
How can Subset Sum be in CoNP?
Viewed 0 times
conpcanhowsumsubset
Problem
On Wikipedia it is Written: NP and co-NP are also thought to be unequal.[1] If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.[2]
So Subset Sum is NP-complete (given integers find a Subset that sums to 0).
CoNp is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier.
What does No mean here in the subset sum Example? I can trivally Test if there is a subset that Doesnt sum to Zero.
So Subset Sum is NP-complete (given integers find a Subset that sums to 0).
CoNp is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier.
What does No mean here in the subset sum Example? I can trivally Test if there is a subset that Doesnt sum to Zero.
Solution
A $\mathrm{No}$ answer means that there is no solution, not that there is a non-solution.
So for Subset-Sum this means there is no subset of the input integers that sum to zero, or to put it another way, every possible (non-trivial) subset has a non-zero sum. Not that there is a subset which doesn't sum to zero.
So for Subset-Sum this means there is no subset of the input integers that sum to zero, or to put it another way, every possible (non-trivial) subset has a non-zero sum. Not that there is a subset which doesn't sum to zero.
Context
StackExchange Computer Science Q#71226, answer score: 5
Revisions (0)
No revisions yet.