3
$\begingroup$

I saw in an answer to this post that it is possible to construct 3-sat clauses with extra variables such that the number of positive and negative literals for each variable are equal. Does anyone know of a construction for 2-sat instances to accomplish this or know it to be impossible? I have been trying, but all I have been able to achieve is narrowing it down to the case where each variable occurs exactly 3 times using the same construction accomplishing this for general SAT. Then of course the difference between positive and negative literals would be exactly 1.

$\endgroup$
  • $\begingroup$ What is your requirement for how the transformed formula must be related to the original formula? (If you just want it to be satisfiable iff the original formula is, then there are probably trivial solutions: solve the 2-sat instance to find out whether it is satisfiable, then depending upon the answer, output either True or False as your formula.) $\endgroup$ – D.W. Jul 27 '15 at 16:45
  • $\begingroup$ @D.W. I am looking for it to be satisfiable iff the original is. I was asking mainly because it might help solve max-2-sat in a more optimal way. Sorry, I guess I should have mentioned that up front. $\endgroup$ – Ari Jul 27 '15 at 18:44
  • $\begingroup$ FWIW, playing with a lot of 2-SAT formulae, my strong intuition is that this is impossible due to a parity problem. I think I could prove it, if I was back in college. But my brain has depreciated a bit much. $\endgroup$ – user35908 Jul 28 '15 at 19:54
  • $\begingroup$ Note that if it was possible to contrive an imbalanced 2-SAT formula that always evaluates the same number of clauses as true regardless of its inputs, then you might be able to use it to balance a problem while shifting its MAX-2-SAT solution by a constant number of clauses (thus enabling you to recover the original solution). I was going to write a program to exhaustively search for the existence of such an imbalanced 2-SAT formula, but the permutations are pretty massive. $\endgroup$ – user35908 Jul 28 '15 at 19:54

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.