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"?

    bool result = PARTITION(J);
    return !result;

Why isn't this algorithm valid, therefore proving that "Co-Partition" is in NP?

Thanks for your help!

  • 2
    $\begingroup$ What is the definition of NP? Check if this algorithm satisfies it. Is it true that for every "yes" instance there exist non-deterministic choices that make the machine accept? Is it true that no non-deterministic choice makes the machine accept any "no" instance? $\endgroup$ – Sasho Nikolov Jul 3 '17 at 22:48
  • $\begingroup$ Could you expand on this? Is the problem here that a non-deterministic algorithm "guesses" an instance (makes a choice), and could therefore make the "wrong" choice, although a right one exists? Is a choice only made once - instead of going through all choices - if you write it like this? $\endgroup$ – user45961 Jul 3 '17 at 23:53
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Jul 4 '17 at 0:05
  • $\begingroup$ @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'? $\endgroup$ – Steven Stadnicki Jul 4 '17 at 0:06
  • 1
    $\begingroup$ You should ask this question at CS.SE (the non-research-level site). The excercise is meant to show you that non-det. machines cannot be trivially "negated", but the pseudo-code is somewhat deceiptive in that it makes you think that PARTITION always answers "yes" if J is a "yes" instance and "no" otherwise. Instead, being non-deterministic, PARTITION answers "yes" or "no" unpredictably, with the only guarantee that it may answer "yes" if J is a "yes" instance, and will always answer "no" if it's a "no" instance. Is this behavior preserved by negation? $\endgroup$ – Damiano Mazza Jul 4 '17 at 6:27