2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.