<p>I don't know the Multicolored Clique Problem suggested by Daniello, however there is a simple reduction from 3SAT:</p>

<p>Given a 3SAT formula $\varphi$ over $n$ variables $x_1,...,x_n$; for each $x_i$ add two variables:</p>

<ul>
<li>$y_{i}^T$ that represents $x_i = true$, and</li>
<li>$y_{i}^F$ that represents $x_i = false$</li>
</ul>

<p>and add the clause $(\neg y_{i}^T \lor \neg y_{i}^F)$ that represents the condition that $x_i$ cannot be both true and false.</p>

<p>Finally replace every clause   $C_j = (l_{j1} \lor l_{j2} \lor l_{j3})$ of $\varphi$ with a clause made of three positive literals $(y_{j1}^a \lor y_{j2}^b \lor y_{j3}^c)$ where:</p>

<ul>
<li>$a = T$ if $l_{j1}= x_{j1}$, $b=F$ if $l_{j1} = \neg x_{j1}$</li>
<li>$b = T$ if $l_{j2}= x_{j2}$, $b=F$ if $l_{j2} = \neg x_{j2}$</li>
<li>$c = T$ if $l_{j3}= x_{j3}$, $b=F$ if $l_{j3} = \neg x_{j3}$</li>
</ul>

<p>For example $(x_1 \lor \neg x_2 \lor \neg x_3)$ becomes: $(y_1^T \lor y_2^F \lor y_3^F)$</p>

<p><strong>Update:</strong></p>

<p>In order to make every positive literal $y_i$ (that can be $y_i^T$ or $y_i^F$) occur only once in the upper part, you can use the following technique:</p>

<p>Suppose that $y_i$ occurs twice, then you can simply replace the two occurrences with two new positive variables: $y_i'$ and $y_i''$ and add the conditions for: $y_i' \leftrightarrow y_i''$:</p>

<p>$$(\neg y_i' \lor y_i'') \land (\neg y_i'' \lor y_i')$$</p>

<p>At this point repeat the split procedure ($y_i'$ becomes $y_i^{T'}$ and $\neg y_i'$ becomes $y_i^{F'}$):</p>

<p>$$(\neg y_i^{T'} \lor \neg y_i^{F''}) \land (\neg y_i^{T''} \lor \neg y_i^{F'}) \land (y_i^{T'} \lor y_i^{F'}) \land (y_i^{T''} \lor y_i^{F''}) $$</p>

<p>and add a dum clause to the upper part in order to include the $y_i^{F'}$ and  $y_i^{F''}$, for example: $(y_i^{F'} \lor y_i^{F''} \lor z_i)$, where $z_i$ is a new variable that can make the clause true.</p>

<p>If $y_i$ occurs more than twice the procedure is similar.</p>

CC BY-SA 3.0
2014-11-02T11:33:01.873Z
Note that the variables in the positive part should all be distinct
Guest1444
CC BY-SA 3.0
2014-11-02T16:15:37.273Z
@Guest1444: ops, I didn't notice it. In that case it is enough to replace two (or more) positive occurrences of $y_i^T$ with two (or more) variables $y_i^{T'}, y_i^{T''}$ and add the clauses for $y_i^{T'} \leftrightarrow y_i^{T''}$: $(\neg y_i^{T'} \lor \neg y_i^{F''})$ and  $(\neg y_i^{T''} \lor \neg y_i^{F'})$ ...(and add "dum" clauses to "include" $y_i^{F'}$ and $y_i^{F''}$ in the upper part; but the reduction is no more so straightforward :-S (I'll fix the answer tomorrow)
Marzio De Biasi
CC BY-SA 3.0
2014-11-01T20:05:30.063Z
2014-11-04T09:52:02.267Z
2014-11-04T09:52:02.267Z
Marzio De Biasi
<p>I'm wondering whether the following SAT variant is NP-complete or polynomial.
The formula given in input has n*m variables, and it has two parts.</p>

<p>A part with the n positive clauses:
$$(x_{1,1} \lor \dots \lor x_{1,m}) \land \\\dots\\(x_{n,1} \lor \dots \lor x_{n,m})$$</p>

<p>And a part with negative clauses with two variables:
$$ \neg x_{i,j} \lor \neg x_{k,l} $$ where $x_{i,j}$ and $x_{k,l}$ are part of the n*m variables mentioned above.</p>

<p>Thank you for the help</p>

CC BY-SA 3.0
2014-10-31T23:01:37.630Z
You say "almost" disjoint clauses. Does this mean that the number/structure of the two-variable clauses is somehow limited?
Niel de Beaudrap
CC BY-SA 3.0
2014-10-31T23:55:16.937Z
This is NP-complete since it is equivalent to the multicolored clique problem.
daniello
CC BY-SA 3.0
2014-11-01T08:35:04.727Z
No there is no restriction on the negative part (I said almost disjoint because the clauses is the positive part are disjoint) Thanks I'll look up the multicolored clique problem
Guest1444
CC BY-SA 3.0
2014-11-02T11:36:14.000Z
I guess in the graph for the multicolor clique, there is going to be an edge between two variables if they don't appear together in the negative part. Do you have a reference for the multicolor clique problem, when it is restricted to complements of interval graphs or to interval graphs (P or NP)?
Guest1444
<cc.complexity-theory>
SAT variant with almost disjoint clauses
Guest1444
# SAT variant with almost disjoint clauses

(Asked by: username_0 on 2014-10-31)

I'm wondering whether the following SAT variant is NP-complete or polynomial.
The formula given in input has n\*m variables, and it has two parts.

A part with the n positive clauses:
$$(x\_{1,1} \lor \dots \lor x\_{1,m}) \land \\\dots\\(x\_{n,1} \lor \dots \lor x\_{n,m})$$

And a part with negative clauses with two variables:
$$ \neg x\_{i,j} \lor \neg x\_{k,l} $$ where $x\_{i,j}$ and $x\_{k,l}$ are part of the n\*m variables mentioned above.

Thank you for the help

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: You say "almost" disjoint clauses. Does this mean that the number/structure of the two-variable clauses is somehow limited?  
> **username_2**: This is NP-complete since it is equivalent to the multicolored clique problem.  
> **username_0**: No there is no restriction on the negative part (I said almost disjoint because the clauses is the positive part are disjoint) Thanks I'll look up the multicolored clique problem  
> **username_0**: I guess in the graph for the multicolor clique, there is going to be an edge between two variables if they don't appear together in the negative part. Do you have a reference for the multicolor clique problem, when it is restricted to complements of interval graphs or to interval graphs (P or NP)?  

---

## 1 answers

### Answer by username_3 on 2014-11-01. Score: 4

I don't know the Multicolored Clique Problem suggested by Daniello, however there is a simple reduction from 3SAT:

Given a 3SAT formula $\varphi$ over $n$ variables $x\_1,...,x\_n$; for each $x\_i$ add two variables:

* $y\_{i}^T$ that represents $x\_i = true$, and
* $y\_{i}^F$ that represents $x\_i = false$

and add the clause $(\neg y\_{i}^T \lor \neg y\_{i}^F)$ that represents the condition that $x\_i$ cannot be both true and false.

Finally replace every clause $C\_j = (l\_{j1} \lor l\_{j2} \lor l\_{j3})$ of $\varphi$ with a clause made of three positive literals $(y\_{j1}^a \lor y\_{j2}^b \lor y\_{j3}^c)$ where:

* $a = T$ if $l\_{j1}= x\_{j1}$, $b=F$ if $l\_{j1} = \neg x\_{j1}$
* $b = T$ if $l\_{j2}= x\_{j2}$, $b=F$ if $l\_{j2} = \neg x\_{j2}$
* $c = T$ if $l\_{j3}= x\_{j3}$, $b=F$ if $l\_{j3} = \neg x\_{j3}$

For example $(x\_1 \lor \neg x\_2 \lor \neg x\_3)$ becomes: $(y\_1^T \lor y\_2^F \lor y\_3^F)$

**Update:**

In order to make every positive literal $y\_i$ (that can be $y\_i^T$ or $y\_i^F$) occur only once in the upper part, you can use the following technique:

Suppose that $y\_i$ occurs twice, then you can simply replace the two occurrences with two new positive variables: $y\_i'$ and $y\_i''$ and add the conditions for: $y\_i' \leftrightarrow y\_i''$:

$$(\neg y\_i' \lor y\_i'') \land (\neg y\_i'' \lor y\_i')$$

At this point repeat the split procedure ($y\_i'$ becomes $y\_i^{T'}$ and $\neg y\_i'$ becomes $y\_i^{F'}$):

$$(\neg y\_i^{T'} \lor \neg y\_i^{F''}) \land (\neg y\_i^{T''} \lor \neg y\_i^{F'}) \land (y\_i^{T'} \lor y\_i^{F'}) \land (y\_i^{T''} \lor y\_i^{F''}) $$

and add a dum clause to the upper part in order to include the $y\_i^{F'}$ and $y\_i^{F''}$, for example: $(y\_i^{F'} \lor y\_i^{F''} \lor z\_i)$, where $z\_i$ is a new variable that can make the clause true.

If $y\_i$ occurs more than twice the procedure is similar.

> **Comments:**
> **username_0**: Note that the variables in the positive part should all be distinct  
> **username_3**: @Guest1444: ops, I didn't notice it. In that case it is enough to replace two (or more) positive occurrences of $y_i^T$ with two (or more) variables $y_i^{T'}, y_i^{T''}$ and add the clauses for $y_i^{T'} \leftrightarrow y_i^{T''}$: $(\neg y_i^{T'} \lor \neg y_i^{F''})$ and  $(\neg y_i^{T''} \lor \neg y_i^{F'})$ ...(and add "dum" clauses to "include" $y_i^{F'}$ and $y_i^{F''}$ in the upper part; but the reduction is no more so straightforward :-S (I'll fix the answer tomorrow)  

---

