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
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.
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.
