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

<p>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$?</p>

<p>Now suppose $PARTITION$ is a non-deterministic, polynomial algorithm that decides the <em>Partition</em>-Problem, which should be the complement of the <em>"Co-Partition"</em>-Problem as defined above.</p>

<p>Shouldn't this be a non-deterministic, polynomial algorithm that decides <em>"Co-Partition"</em>?</p>

<pre><code>NON_PARTITION(J)
    bool result = PARTITION(J);
    return !result;
</code></pre>

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

<p>Thanks for your help!</p>

CC BY-SA 3.0
2017-07-03T22:48:05.990Z
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?
Sasho Nikolov
CC BY-SA 3.0
2017-07-03T23:53:41.723Z
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?
user45961
CC BY-SA 3.0
2017-07-04T00:05:16.240Z
@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
CC BY-SA 3.0
2017-07-04T00:06:06.077Z
@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
CC BY-SA 3.0
2017-07-04T06:27:34.480Z
You should ask this question at [CS.SE](https://cs.stackexchange.com/) (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?
Damiano Mazza
<cc.complexity-theory><complexity-classes><np>
Co-Partition Problem: Why is this proof for it being in NP wrong?
user45961
# Co-Partition Problem: Why is this proof for it being in NP wrong?

(Asked by: username_0 on 2017-07-03)

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!

**Tags:** cc.complexity-theory, complexity-classes, np

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_2**: @username_0 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.  
> **username_2**: @username_0 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'?  
> **username_3**: You should ask this question at [CS.SE](https://cs.stackexchange.com/) (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?  

---

## 0 answers

