-4
$\begingroup$

I am trying to reduce 3-sat to 2-sat. With my reduction, I can find one assignment that satisfies them both, but there are some assignments that satisfy only the 3-sat.

Does it make my reduction invalid? Is 3-sat required to be equal-satisfiable to 2-sat to call it a reduction?

Improve this question
$\endgroup$
2
$\begingroup$

For a reduction $f:\Sigma^{\ast}_{\Pi_{1}}\rightarrow \Sigma^{\ast}_{\Pi_{2}}$ from language $\Pi_{1}$ to $\Pi_{2}$ to be valid you have to prove that if $I\in \Pi_{1}$ then $f(I) \in \Pi_{2}$ and that if $f(I) \in \Pi_{2}$ then $I\in \Pi_{1}$.

Mathematically, you don't have to show how to get the solution of one from the other, just that if a solution for one exists, then a solution for the other has to as well (in both directions).

Practically of course, a reduction normally has a constructive way of doing this, i.e. if someone gave you the solution for either $I$ or $f(I)$, you would be able to produce the solution for the other.

Now in your specific case, what you would need to show is that, given any 3-SAT instance, if there's a satisfying assignment for the 3-SAT instance, then there's a satisfying assignment for the 2-SAT instance it maps to and vice versa. However I don't see how you can say you've found an assignment for the formulae - the reduction should work for every possible 3-SAT instance (that's the whole point), so there's no way you can know enough about the input to solve it, because it's not a specific, concrete formula.

Or to put it another way, if what you've got is a conversion between a specific boolean formula in 3-CNF to a specific boolean formula in 2-CNF, then you don't have a reduction from 3-SAT to 2-SAT, you only have a mapping between two particular formulae.

Lastly, attempting this reduction doesn't seem productive. This reduction cannot be polynomial-time computable unless $P=NP$. If it is only exponential-time computable, it's possible, but useless because there's a trivial reduction, you can simply solve 3-SAT in that amount of time, there's no need to convert it to a 2-SAT instance then solve that instead.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Now you made me even more confused, lol. Please make a difference between: Any assignment that will satisfy specific 3-sat formula must satisfy specific 2-sat formula if it's a reduction from 3-sat they must be equal-satisfiable. To: If specific 3-sat and 2-sat formulas satisfies for the same assignment(2-sat may have more variables than 3-sat) then 3-ast been reduced to 2-sat, they may be not equal-satisfiable. Also you are welcome to read my first question about this. $\endgroup$ – Ilya Gazman Dec 6 '13 at 13:39
  • $\begingroup$ I'm not sure I agree with the way you defined a reduction; if $f$ is a function $\Pi_1 \rightarrow \Pi_2$ then it is only defined on inputs $I \in \Pi_1$ and can only give outputs $f(I) \in \Pi_2$. The usual definition covers a universe $U_1$ of (syntactically) valid instances of problem $1$ and a universe $U_2$ of (syntactically) valid instances of problem $2$, then defines the reduction as $f: U_1 \rightarrow U_2$. To reduce language $L_1 \subseteq U_1$ to $L_2 \subseteq U_2$ we then need that $\forall x \in U_1: x \in L_1 \leftrightarrow f(x) \in L_2$. $\endgroup$ – G. Bach Dec 6 '13 at 14:08
  • $\begingroup$ @G.Bach, quite right. Let this be a lesson to all. Don't stackexchange at 2 in the morning ;). $\endgroup$ – Luke Mathieson Dec 7 '13 at 1:57
  • $\begingroup$ @Babibu, you don't (necessarily) have to use the same assignment for both. What you have to show is that the existence of a satisfying assignment for the input to $f$ exists if and only if a satisfying assignment for the output of $f$ exists. It may happen to be that they are the same, but this will depend on the actual details of $f$. The Wikipeda article on equisatisfiability says it quite well too: "Two equisatisfiable formulae may have different models, provided they both have some or both have none." $\endgroup$ – Luke Mathieson Dec 7 '13 at 2:02
5
$\begingroup$

We went through this yesterday. The only property required for a reduction from 3SAT to 2SAT is that it maps satisfiable 3CNF formulas to satisfiable 2CNF formulas, and unsatisfiable 3CNF formulas to unsatisfiable 2CNF formulas. There is no other requirement. The formulas do not have to be related in any other way. They don't have to have the same truth table or even the same variables. If the 3CNF formula does happen to have the same variables as the 2CNF formula it's mapped to, there is no requirement whatsoever that an assignment that satisfies the first must satisfy the second, or vice-versa. The only requirement is that, if there is some way of making the 3CNF formula true, there must be some way of making the resulting 2CNF formula true; and if there is no way of making the 3CNF formula true, there must also be no way of making the 2CNF formula true.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thats what I thought yesterday but I been hearing other opinions... So just to be clear: If my 2-CNF formula, have all the variables in 3-CNF and other variables too, and there is an assignment that make 3-CNF to satisfy. It will not make the reduction invalid if I find a satisfiable assignment for 3-CNF that cannot be satisfied in 2-cnf(there is other assignments that make 2-cnf to satisfy) $\endgroup$ – Ilya Gazman Dec 6 '13 at 13:58
  • 4
    $\begingroup$ @Babibu If you read David's answer carefully, then he already answered this question. I'm not sure you properly understand the terminology and/or definitions for propositional logic and reductions. You could spend your time far more productively if you first read up on those subjects. For complexity theory, my class used "Arora & Barak: A Modern Approach to Complexity Theory", although this may be too advanced for beginners. For the basics of logic I would recommend "Discrete Mathematics and its Applications" by Rosen. $\endgroup$ – G. Bach Dec 6 '13 at 14:07
  • 3
    $\begingroup$ @Babibu Read my answer. I wrote twice what the only requirement is. I wrote it at least once yesterday, too. Does that requirement say anything, anything at all, about the clause $(a\vee a)$ having to appear? $\endgroup$ – David Richerby Dec 6 '13 at 14:28
  • 3
    $\begingroup$ 2SAT is the question, "Here is a 2CNF formula: is there any assignment to the variables that makes it true?" The answer is either yes or no: it doesn't tell you what you need to set the variables to. However, if you can work out whether a formula is satisfiable, you can find a satisfying assignment. Ask if it's satisfiable. If yes, set the first variable to true and ask if the new formula is satisfiable. If yes, move to the next variable; if no, the first variable must be false. Now, set the second variable to true, and so on. [continued] $\endgroup$ – David Richerby Dec 6 '13 at 15:20
  • 3
    $\begingroup$ [continued from previous comment] So, if you had a reduction from 3SAT to 2SAT, you could use it to find a satisfying assignment to a 3CNF formula $\phi$ in the same way. Produce the corresponding 2CNF and ask if it's satisfiable. If so, modify $\phi$ to set the first variable to true. Produce the 2CNF formula corresponding to this new formula and ask if it's satisfiable. If so, take the first variable to be true; otherwise, take it to be false. Iterate through the variables of $\phi$ as before. $\endgroup$ – David Richerby Dec 6 '13 at 15:22

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.