So I have this wrong proof that the problem Co-Partition is in NP. I know the proof is wrong because I've encountered it in an educational environment and was told that it's not working. I don't, however, know why.We are given a set of natural numbers $A := \{a_{1}, a_{2}, ..., {a_{n} \}}$. The Co-Partition-Problem is supposed to answer the following question: Does $\sum_{a \in S} a \neq \sum_{a \in A \backslash S}$ hold true for all $S \subseteq A$?Now suppose $PARTITION$ is a non-deterministic, polynomial algorithm that decides the Partition-Problem, which should be the complement of the Co-Partition-Problem as defined above.Shouldn't this be a non-deterministic, polynomial algorithm that decides Co-Partition?NON_PARTITION(J)    bool result = PARTITION(J);    return !result;Why isn't this algorithm valid, therefore proving that Co-Partition is in NP?Thanks for your help!
Co-Partition Problem: Why is this proof for it being in NP wrong?
cc.complexity theory;complexity classes;np