# Co-Partition Problem: Why is this proof for it being in NP wrong? [closed]

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?

• @user45961 That's essentially correct. The best way to think about NP problems is that they satisfy an existence formula: 'there exists some vector $\langle x_0, x_1, x_2, \ldots\rangle$ such that (some polynomial-checkable relation among the $x_n$)'. For instance, the TSP says 'there exists an ordering of cities such that the distance along that path between cities is less than some value'. Satisfaction says 'there exists an assignment of true and false to the $x_i$ such that the formula is satisfied', etc. – Steven Stadnicki Jul 4 '17 at 0:05
• @user45961 Can you understand the distinction between 'there exists an assignment of true and false to the $x_i$ such that the formula is not satisfied' and 'there does not exist an assignment to the $x_i$ such that the formula is satisfied'? – Steven Stadnicki Jul 4 '17 at 0:06