<p>Let me define both the problems first:</p>

<p>$OR$-$SAT$:  $m$ Boolean formulae are given in $CNF$, $\phi_1$,$\phi_2$, $\ldots$, $\phi_m$, each on variable set, $x_1, x_2, \ldots, x_n$. ($m$ $&lt;$ $2^n$, otherwise the problem is polynomial time solvable) Each $\phi_{i}$ is of size at most $poly(n)$.</p>

<p>$Question$: Is there an assignments to the given $n$ variable, such that at least one of the $\phi_i$s is satisfiable ? </p>

<p>$Exact\ CNF$-$SAT$:  A formula $\phi$ in conjunctive normal form of size $m$ over $n$ variables.</p>

<p>$Question$: Is there any satisfiable assignment for $\phi$, such that exactly one of the literals in each clause of $\phi$ is assigned to True ?</p>

<p>I am interested to know if there is a reduction from $OR$-$SAT$ to $Exact\ CNF$-$SAT$, keeping the number of variables polynomially bounded, or if it can be proved, no such reduction possible unless some bad thing happens. There are standard reductions from $OR$-$SAT$ to $SAT$ and $SAT$ to $Exact\ CNF$-$SAT$, but the second reduction doesn't keep the number of variables polynomially bounded. Any thought ??</p>

<p>In $OR$-$SAT$, each $\phi_i$ is of size $poly(n)$. So $SAT$ and $OR$-$SAT$ are pretty much different problems. They are in different levels in $VC$-hierarchy. There are many problems between these 2 levels.  I am actually interested to know the exact position of $Exact$ $CNF$-$SAT$ in that hierarchy. I am interested to bound the number of variables to $poly(n)$, as I am interested in PPT (Parametric Polynomial Time) reduction rather than normal polynomial reduction.</p>

CC BY-SA 3.0
2013-04-16T00:07:48.513Z
Thanks Kaveh, I have edited my question inserting the information I have mentioned above.
David
CC BY-SA 3.0
2013-04-16T06:08:53.250Z
SAT to 3SAT to [ONE-IN-THREE 3SAT](http://en.wikipedia.org/wiki/One-in-three_3SAT) keeps the number of variables polynomially bounded.  Are you looking for something else?
Kyle Jones
CC BY-SA 3.0
2013-04-16T13:52:33.297Z
In the reduction from $SAT$ to $3SAT$, number of variables of the reduced $3SAT$ instance is polynomially bounded to the number of clauses of $SAT$ instance, not number of variables. So, it doesn't help me. In fact, any such reduction from $SAT$ to $3SAT$ is impossible unless Polynomial Hierarchy collapses. Eventually I don't expect any reduction from $OR$-$SAT$ to $Exact$ $CNF$-$SAT$ via $SAT$ maintaining the number of variables polynomially bounded. There should be some direct reduction, but I can't find any.
David
<cc.complexity-theory><np-hardness>
Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?
David
# Reduction from OR-SAT to Exact CNF-SAT, keeping the number of variables polynomially bounded?

(Asked by: username_0 on 2013-04-15)

Let me define both the problems first:

$OR$-$SAT$: $m$ Boolean formulae are given in $CNF$, $\phi\_1$,$\phi\_2$, $\ldots$, $\phi\_m$, each on variable set, $x\_1, x\_2, \ldots, x\_n$. ($m$ $<$ $2^n$, otherwise the problem is polynomial time solvable) Each $\phi\_{i}$ is of size at most $poly(n)$.

$Question$: Is there an assignments to the given $n$ variable, such that at least one of the $\phi\_i$s is satisfiable ?

$Exact\ CNF$-$SAT$: A formula $\phi$ in conjunctive normal form of size $m$ over $n$ variables.

$Question$: Is there any satisfiable assignment for $\phi$, such that exactly one of the literals in each clause of $\phi$ is assigned to True ?

I am interested to know if there is a reduction from $OR$-$SAT$ to $Exact\ CNF$-$SAT$, keeping the number of variables polynomially bounded, or if it can be proved, no such reduction possible unless some bad thing happens. There are standard reductions from $OR$-$SAT$ to $SAT$ and $SAT$ to $Exact\ CNF$-$SAT$, but the second reduction doesn't keep the number of variables polynomially bounded. Any thought ??

In $OR$-$SAT$, each $\phi\_i$ is of size $poly(n)$. So $SAT$ and $OR$-$SAT$ are pretty much different problems. They are in different levels in $VC$-hierarchy. There are many problems between these 2 levels. I am actually interested to know the exact position of $Exact$ $CNF$-$SAT$ in that hierarchy. I am interested to bound the number of variables to $poly(n)$, as I am interested in PPT (Parametric Polynomial Time) reduction rather than normal polynomial reduction.

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

> **Comments:**
> **username_0**: Thanks Kaveh, I have edited my question inserting the information I have mentioned above.  
> **username_1**: SAT to 3SAT to [ONE-IN-THREE 3SAT](http://en.wikipedia.org/wiki/One-in-three_3SAT) keeps the number of variables polynomially bounded.  Are you looking for something else?  
> **username_0**: In the reduction from $SAT$ to $3SAT$, number of variables of the reduced $3SAT$ instance is polynomially bounded to the number of clauses of $SAT$ instance, not number of variables. So, it doesn't help me. In fact, any such reduction from $SAT$ to $3SAT$ is impossible unless Polynomial Hierarchy collapses. Eventually I don't expect any reduction from $OR$-$SAT$ to $Exact$ $CNF$-$SAT$ via $SAT$ maintaining the number of variables polynomially bounded. There should be some direct reduction, but I can't find any.  

---

## 0 answers

