2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks Kaveh, I have edited my question inserting the information I have mentioned above. $\endgroup$ – David Apr 16 '13 at 0:07
  • 2
    $\begingroup$ SAT to 3SAT to ONE-IN-THREE 3SAT keeps the number of variables polynomially bounded. Are you looking for something else? $\endgroup$ – Kyle Jones Apr 16 '13 at 6:08
  • $\begingroup$ 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. $\endgroup$ – David Apr 16 '13 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.