2
$\begingroup$

The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:

For each 3SAT clause: $x+y+z=1$ Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:

  1. $R(x^-, a, b)=1$
  2. $R(y, b, c) =1$
  3. $R(z^-, c, d)=1$

Query: Given a 3SAT instance how can we reduce it into (as simple as possible) 1-in-3SAT instance with the following additional constraints:

  1. All new variables occur in at least 2 clauses.
  2. There are no dummy/redundant clauses in the 1-in-3-SAT reduction. A dummy/redundant clause is whose addition or removal in the problem does not change the set of solutions of the problem. Thus, all clauses are essential.

I have been stuggling with this for some time without much success.

$\endgroup$
5
  • 1
    $\begingroup$ For 1, a stronger property is achieved in cstheory.stackexchange.com/a/42223. For 2, something else is needed. $\endgroup$ Sep 7 at 8:04
  • $\begingroup$ @EmilJeřábek Thank you. It does solve the first part elegantly. For 2. is it correct to state that the new/reduced problem instance has a redundant clause if and only if the original 1 in 3 SAT instance had a redundant clause. The simple reason being that there is a 1 to 1 relation b/w solution space and the set of clauses in second problem uniquely represent the set of clauses in original 1-in-3 SAT? $\endgroup$
    – J.Doe
    Sep 8 at 7:23
  • $\begingroup$ No. In fact, one can check that in the new instance, each of the new clauses is (individually) redundant. $\endgroup$ Sep 8 at 11:27
  • $\begingroup$ @EmilJeřábek I thought about it for a while. One of the clauses $(\neg x, \neg x', F_1)$ and $(x, x', F_1)$ are redundant so we need only one of them. But in that case we are again back to square one as $x'$ will have only 1 occurance. This doesn't seem to work (constraint 2). Can you please help me with this as I am stuck? $\endgroup$
    – J.Doe
    Sep 8 at 16:49
  • $\begingroup$ I cannot help you with this. Condition 2 is extremely strong, and I have no idea if it’s possible to achieve it, even ignoring Condition 1. $\endgroup$ Sep 8 at 17:11
-2
$\begingroup$

Edit: This answers a related problem, in which "as simple as possible" means that the number of clauses is minimal.

Let $A$ be the given 3SAT instance. I will assume that you are looking for a corresponding 1-in-3SAT instance $B$ with as few clauses as possible, rather than some local minimum. It also seems that you restrict yourself to instances $B$ whose variables include those of $A$, plus potentially new variables, and that any satisfying assignment for $B$ is also a satisfying assignment for $A$, and that any satisfying assignment for $A$ can be extended to a satisfying assignment for $B$ using some assignment for the new variables.

Let $c$ be the number of clauses in $B$. If $A$ is not satisfiable, then $B$ will be an unsatisfiable 1-in-3SAT instance of constant length ($c=1$ or $c=2$ depending on whether a single clause can contain a literal and its negation).

We can in polynomial time tell whether $A$ is satisfiable based on $B$ as follows. If $c>2$, then $A$ is satisfiable. If $B$ has length $c$, we can find all its satisfying assignments in $O(c2^{3c})$ time, so if $c\leq 2$, we can find all satisfying assignments in constant time and hence determine whether $A$ is satisfiable. Therefore, a reduction to a 1-in-3SAT instance with a minimum number of clauses is NP-hard.

$\endgroup$
5
  • 1
    $\begingroup$ we don't know if the instance is satisfiable, has a unique solution or more than one solution. I am simply trying to find a reduction from SAT to 1-in-3-SAT but with a couple of additional constraints. I am afraid that this simply does not answer my query! we are not trying to solve the problem but a general reduction without caring about the number of solutions. $\endgroup$
    – J.Doe
    Sep 7 at 4:54
  • $\begingroup$ The point is that any reduction will be able to determine whether an instance is satisfiable, so there is no polynomial time reduction unless P=NP. $\endgroup$
    – Tim
    Sep 7 at 7:17
  • 1
    $\begingroup$ Your argument does not demonstrate anything like that. In particular, it is perfectly possible that the reduction has linear size even if the input formula is unsatisfiable. Your argument didn’t use anything special about 1-in-3-SAT; if it worked, it would also show that e.g. a reduction from 3-SAT to 3-SAT is impossible, which is clearly absurd. $\endgroup$ Sep 7 at 8:01
  • $\begingroup$ My answer shows that a globally minimal 1-in-3SAT instance is hard to find, but I believe that J.Doe is only looking for a locally minimal instance. The impossibility of a 3-SAT to 3-SAT reduction is not absurd, as it involves figuring out whether some clause is redundant. $\endgroup$
    – Tim
    Sep 7 at 8:18
  • $\begingroup$ The question does not ask for a globally or locally minimal instance. It asks whether a reduction satisfying 1 and 2 exists in the first place; if it does, you may start worrying whether it’s possible to make it simpler. This does not answer the question at all. $\endgroup$ Sep 7 at 9:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.