<p>Turning my comment to an answer:
The problem you describe is known as Not All Equal SAT (NAE-SAT), but is phrased differently. A NAE assignment for a CNF-formula $\phi$ over variables is one where in each clause there is at least one false variable and one true variable.</p>

<p>It is easy to see that an assignment is NAE iff its inverse is also NAE.</p>

<p>Showing that NAE-SAT is NP-complete is a well-known exercise, and it can be easily solved by splitting it to two parts.</p>

<p>First, given a 3-CNF formula, we can convert it to a 4-CNF formula by adding a variable $w$ and converting every clause of the form $(x\vee y\vee z)$ to $(x\vee y\vee z\vee w)$.</p>

<p>It is easy to see that the original formula is satisfiable iff the resulting formula is in NAE-SAT.</p>

<p>Then, standard techniques can be used to convert this formula back to 3-CNF, while maintaining the NAE property.</p>

CC BY-SA 3.0
2015-07-13T12:06:13.010Z
2015-07-13T12:06:13.010Z
Shaull
<p>Here is a variant of the SAT problem in which a satisfying assignment must have additional properties.<br>
<strong>Input:</strong> A 3-CNF formula $f$ with variables $x_{1\dots k}$.<br>
<strong>Output:</strong> 
For an assignment $S$ of $x_{1\dots k}$, let $\overline S$ be defined such that $x_i=true$ in $\overline S$ if and only if $x_i=false$ in $S$.
Is there an assignment $S$ such that both $f(S)$ and $f(\overline S)$ hold?</p>

<p>Is this problem still NP-hard?</p>

<p><strong>Examples:</strong></p>

<ol>
<li>$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)\land(x_1\lor \neg x_2\lor \neg x_3)$<br>
This requires $x_1=true$ in $S$, but then $x_1=false$ in $\overline S$, so $f(S)$ and $f(\overline S)$ cannot simultaneously hold.</li>
<li>$f=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor \neg x_3)\land(x_1\lor \neg x_2\lor x_3)$<br>
$S=\{x_1:true,~x_2:false,~x_3:false\}$<br>
$\overline S=\{x_1:false,~x_2:true,~x_3:true\}$<br>
Then both $f(S)$ and $f(\overline S)$ hold.</li>
</ol>

CC BY-SA 3.0
2015-07-12T09:08:27.320Z
This is the *Not-all-equal* SAT problem (or NAE-SAT), and it is well known to be NP-complete (e.g. [The first result in google](https://people.cs.umass.edu/~barring/cs611/lecture/17.pdf))
Shaull
CC BY-SA 3.0
2015-07-12T09:21:00.530Z
NAE-SAT requires each clause to have both a positive and negative assignment, which is a different problem. There could well be a NAE-SAT instance with a unique satisfying assignment, while for this problem there must always be at least two.
Tim
CC BY-SA 3.0
2015-07-12T09:43:26.520Z
Nope. For every NAE assignment, it's complement is also a NAE assignment.
Shaull
CC BY-SA 3.0
2015-07-12T10:06:31.207Z
That makes sense, I suppose that answers the question.
Tim
CC BY-SA 3.0
2015-07-13T10:42:35.773Z
@Shaull, what you're saying is not consistent with the source you're citing. It says: _Here the input is a formula in 3-CNF, but the formula is “satisfied” only if there is both a true literal and a false literal in each clause._ This is not the same as being asked. For instance, $(z\lor x\lor y)\land(\lnot x\lor y)$, set $y=1$,$z=0$,$x=1$. But $y$ cannot be flipped.
Mikolas
CC BY-SA 3.0
2015-07-13T10:49:50.410Z
@Tim, I think I have a reduction from SAT to "opposite-solution SAT" but to "opposite-solution 3SAT" seems harder. Does it matter that it's 3SAT?
Mikolas
CC BY-SA 3.0
2015-07-13T11:09:53.247Z
@Mikolas, Shaull is right, an assignment with both a true and false literal in each clause can be flipped (which makes the initially false literal true, so all clauses are still satisfied).
Tim
CC BY-SA 3.0
2015-07-13T11:54:06.377Z
Tim, @Shaull. You guys are right. Nice observation. The example I gave is wrong. BTW the reduction seems easy. For each original variable $x$ introduce a fresh one $x'=\lnot x$ and create a copy of the original problem using $x'$ variables. It is also possible to convert to 4-SAT by adding only 1 variable $r$: create a copy of the problem with all polarities flipped; add $r$ to all clauses of one copy and $\lnot r$ to the other one.
Mikolas
<cc.complexity-theory><np-hardness><sat>
Is SAT with two "opposite" solutions NP-hard?
Tim
# Is SAT with two "opposite" solutions NP-hard?

(Asked by: username_0 on 2015-07-12)

Here is a variant of the SAT problem in which a satisfying assignment must have additional properties.  
**Input:** A 3-CNF formula $f$ with variables $x\_{1\dots k}$.  
**Output:**
For an assignment $S$ of $x\_{1\dots k}$, let $\overline S$ be defined such that $x\_i=true$ in $\overline S$ if and only if $x\_i=false$ in $S$.
Is there an assignment $S$ such that both $f(S)$ and $f(\overline S)$ hold?

Is this problem still NP-hard?

**Examples:**

1. $f=(x\_1\lor x\_2\lor x\_3)\land(x\_1\lor x\_2\lor \neg x\_3)\land(x\_1\lor \neg x\_2\lor x\_3)\land(x\_1\lor \neg x\_2\lor \neg x\_3)$  
   This requires $x\_1=true$ in $S$, but then $x\_1=false$ in $\overline S$, so $f(S)$ and $f(\overline S)$ cannot simultaneously hold.
2. $f=(x\_1\lor x\_2\lor x\_3)\land(x\_1\lor x\_2\lor \neg x\_3)\land(x\_1\lor \neg x\_2\lor x\_3)$  
   $S=\{x\_1:true,~x\_2:false,~x\_3:false\}$  
   $\overline S=\{x\_1:false,~x\_2:true,~x\_3:true\}$  
   Then both $f(S)$ and $f(\overline S)$ hold.

**Tags:** cc.complexity-theory, np-hardness, sat

> **Comments:**
> **username_1**: This is the *Not-all-equal* SAT problem (or NAE-SAT), and it is well known to be NP-complete (e.g. [The first result in google](https://people.cs.umass.edu/~barring/cs611/lecture/17.pdf))  
> **username_0**: NAE-SAT requires each clause to have both a positive and negative assignment, which is a different problem. There could well be a NAE-SAT instance with a unique satisfying assignment, while for this problem there must always be at least two.  
> **username_1**: Nope. For every NAE assignment, it's complement is also a NAE assignment.  
> **username_0**: That makes sense, I suppose that answers the question.  
> **username_2**: @username_1, what you're saying is not consistent with the source you're citing. It says: _Here the input is a formula in 3-CNF, but the formula is “satisfied” only if there is both a true literal and a false literal in each clause._ This is not the same as being asked. For instance, $(z\lor x\lor y)\land(\lnot x\lor y)$, set $y=1$,$z=0$,$x=1$. But $y$ cannot be flipped.  
> **username_2**: @username_0, I think I have a reduction from SAT to "opposite-solution SAT" but to "opposite-solution 3SAT" seems harder. Does it matter that it's 3SAT?  
> **username_0**: @username_2, username_1 is right, an assignment with both a true and false literal in each clause can be flipped (which makes the initially false literal true, so all clauses are still satisfied).  
> **username_2**: username_0, @username_1. You guys are right. Nice observation. The example I gave is wrong. BTW the reduction seems easy. For each original variable $x$ introduce a fresh one $x'=\lnot x$ and create a copy of the original problem using $x'$ variables. It is also possible to convert to 4-SAT by adding only 1 variable $r$: create a copy of the problem with all polarities flipped; add $r$ to all clauses of one copy and $\lnot r$ to the other one.  

---

## 1 answers

### Answer by username_1 on 2015-07-13. Score: 9 | Accepted answer

Turning my comment to an answer:
The problem you describe is known as Not All Equal SAT (NAE-SAT), but is phrased differently. A NAE assignment for a CNF-formula $\phi$ over variables is one where in each clause there is at least one false variable and one true variable.

It is easy to see that an assignment is NAE iff its inverse is also NAE.

Showing that NAE-SAT is NP-complete is a well-known exercise, and it can be easily solved by splitting it to two parts.

First, given a 3-CNF formula, we can convert it to a 4-CNF formula by adding a variable $w$ and converting every clause of the form $(x\vee y\vee z)$ to $(x\vee y\vee z\vee w)$.

It is easy to see that the original formula is satisfiable iff the resulting formula is in NAE-SAT.

Then, standard techniques can be used to convert this formula back to 3-CNF, while maintaining the NAE property.


---

