3
$\begingroup$

It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it.

So you can state that there is no such reduction from 3-SAT to 2-SAT unless $P=NP$.

I am looking for strong proof for this state, regardless NP belong to P or not.

|cite|improve this question
$\endgroup$
11
$\begingroup$

You can prove it by contradiction:

Suppose that $P \neq NP$ and there is a polynomial-time reduction from 3-SAT to 2-SAT; then 2-SAT is NP-complete, but 2-SAT is also solvable in polynomial time, so for all decision problems $A \in NP$ you can decide $x \in A$ reducing $x$ to the corresponding 2-SAT instance in polynomial time and solve it in polynomial time (and the total time is still polynomial); so $A \in P$ and hence $NP \subseteq P$. But we also have $P \subseteq NP$, so $P = NP$ which is a contradiction. :-)

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If $P \neq NP$, there could not be a polynomial-time reduction from 3-SAT to 2-SAT, you cannot make assumption for both $P \neq NP$ and there is a polynomial reduction from 3-sat to 2-sat. $\endgroup$ – Ilya Gazman Dec 5 '13 at 15:34
  • 2
    $\begingroup$ @Babibu: he is showing what you asked for. "There is no reduction from 3-SAT to 2-SAT unless P = NP" is equivalent to "If there is a reduction from 3-SAT to 2-SAT, then P = NP", which is equivalent to "If P $\ne$ NP, then there is no reduction from 3-SAT to 2-SAT". $\endgroup$ – Niel de Beaudrap Dec 5 '13 at 15:45
  • 3
    $\begingroup$ @Babibu: if you prove it then you would solve the P vs NP question :-) $\endgroup$ – Vor Dec 5 '13 at 15:49
  • 1
    $\begingroup$ @Babibu: You might want to specify what sort of reduction you want. Do you want not only a many-to-one reduction, but a reduction which preserves the number of satisfying assignments? Or perhaps one which preserves the set of satisfying assignments? $\endgroup$ – Niel de Beaudrap Dec 5 '13 at 15:54
  • 1
    $\begingroup$ @Babibu (It is also worth noting that yes, it is obvious that a many-to-one reduction from 3-SAT to 2-SAT exists if and only if P=NP. The problem is that it is not nearly as easy as you seem to think, to prove that there is no such many-to-one reduction.) $\endgroup$ – Niel de Beaudrap Dec 5 '13 at 15:56
0
$\begingroup$

one could provably use 2SAT to solve 3SAT problems, ie a reduction, its just that there is not a P-time/space reduction unless P=NP. in other words, converting 3SAT to 2SAT, or reducing 3SAT instance $A$ to 2SAT instance $B$, is indeed possible (using extra 2SAT variables and clauses!), but all known techniques lead to an "exponential blowup" in the size of $B$ wrt $A$ (ie space which also implies time). this shows how important it is to measure time/space requirements of a reduction and in fact there are many different ways to measure the complexity of a reduction. P-Time reductions are just more basic/common but many more complex "reduction complexities" are studied. so in this case in fact a P-time reduction from 3SAT to 2SAT exists iff P=NP...

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ ps the 3SAT/2SAT dichotomy is indeed an interesting way to try to understand the P=?NP question, and also relates to an important phenomenon in the field known as the transition point where instances move from P-time solveable to non-P-time solvable. $\endgroup$ – vzn Dec 5 '13 at 20:00
  • 2
    $\begingroup$ There's certainly a P-space reduction: solve the 3SAT instance in the reduction and map to true or false, as appropriate. $\endgroup$ – David Richerby Dec 5 '13 at 20:44
  • 1
    $\begingroup$ Why does anyone care about a nontrivial EXPSPACE reduction for a problem that can trivially be done in polynomial space? $\endgroup$ – David Richerby Nov 27 '14 at 10:03
  • 1
    $\begingroup$ Let me try again. You are telling us about a new reduction from 3SAT to 2SAT. We already know that such a reduction exists: in fact, it's obvious that one exists and that infinitely many exist. So, for your new reduction to be interesting, it must be somehow "better" than the existing reduction. Your new reduction is considerably less efficient than the known one, since it requires exponential, rather than polynomial space. It is also much more complicated. It produces a larger output. What properties does it have that compensate for all of this? $\endgroup$ – David Richerby Nov 27 '14 at 15:40
  • 1
    $\begingroup$ update, SG has turned this into a cstheory question (thx for that). my intuition could be off, have to think about this more based on those comments that say not all Boolean functions are expressible in 2SAT, never noticed that before. by the way, see the confusion. am looking at 2SAT/3SAT in terms of characterizing sets of bitvector solutions in this answer, not as decision problems per se. $\endgroup$ – vzn Nov 28 '14 at 22:43

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.