8
$\begingroup$

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its corresponding #MONOTONE-2SAT instance $F'$?

A second question is: let $K'$ be the number of solutions of $F'$, and let $K$ be the number of solutions of $F$. Does $K' = K$? Or we must use a back transformation that converts $K'$ to $K$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Could you please motivate why did you vote against this question? $\endgroup$
    – Giorgio Camerani
    Sep 13 '10 at 9:04
  • $\begingroup$ I am not the one who voted the question down, but I will not be surprised if someone considers that the question is too basic. $\endgroup$
    – Tsuyoshi Ito
    Sep 13 '10 at 11:40
  • $\begingroup$ I dont' think so. It's not more basic than some other questions raised on this website. Anyhow a question, even if basic, may nonetheless be helpful. My questions about lower bounds on #SAT and on SAT solution clusters may be considered very basic as well, but they were not voted down. $\endgroup$
    – Giorgio Camerani
    Sep 13 '10 at 11:58
  • $\begingroup$ The first question is pretty basic: essentially you asked what a reduction was. The second question has trapped me once, too, but it is resolved by thinking in the right way. The whole point of my answer is that the question is easy. If you still think that the question is at the right level after reading my answer, probably my answer is written poorly. $\endgroup$
    – Tsuyoshi Ito
    Sep 13 '10 at 12:16
  • 1
    $\begingroup$ Walter, Tsuyoshi, while this discussion is helpful, a better place for it is on meta.cstheory.stackexchange.com. Why don't you discuss this there, and add a link to that discussion here. FWIW, I think the question is relatively harmless, but a bit more of "why I'm asking" would have been helpful. $\endgroup$
    – Suresh Venkat
    Sep 13 '10 at 16:06
7
$\begingroup$

As for the first question, that is what a reduction does. For how to reduce #3SAT to #Monotone-2SAT, see the proof of #P-completeness of #Monotone-2SAT [Val79b], which is based on the #P-completeness of Permanent [Val79a]. To reduce #SAT to #3SAT, Cook’s reduction from any problem in NP to 3SAT is parsimonious and therefore reduces #SAT to #3SAT.

The answer to the second question is no. The reduction in [Val79a] from #3SAT to Permanent does not preserve the number of solutions. Moreover, if a reduction from #SAT to #Monotone-2SAT (or Permanent) which preserves the number of solutions were known, the same reduction would reduce the decision version of SAT to the decision version of Monotone-2SAT (or Bipartite Matching), implying P=NP.

References

[Val79a] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189–201, 1979. http://dx.doi.org/10.1016/0304-3975(79)90044-6

[Val79b] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, Aug. 1979. http://dx.doi.org/10.1137/0208032

Improve this answer
$\endgroup$
15
  • $\begingroup$ Thanks for your pointers to [Val79b] and [Val79a]. For what concerns the second answer, I can't understand it: if a problem is #P-complete it can be used to solve any other problem in #P. Now suppose I want to solve #SAT: I want to know the number K of solutions of a given formula F; in order to do so, I reduce F to an instance F' of #MONOTONE-2SAT, then I obtain the number K' of solutions to F'. Now, if knowing K' doesn't help me in knowing K (i.e. solving #MONOTONE-2SAT doesn't help me to solve #SAT) how can #MONOTONE-2SAT be #P-complete? Why shall I do all this if it doesn't solve #SAT? $\endgroup$
    – Giorgio Camerani
    Sep 13 '10 at 12:09
  • $\begingroup$ Let me express a side comment. Is it possible that I have to pay 40 dollars to read an article which is 31 years old? I find this absurd and against the spirit of science. I would agree if the article was 10-15 years old, as it can be considered as a "patented" discovery. But paying for a 31 years old article is a shame IMHO. Could anyone point me to a free version of it? $\endgroup$
    – Giorgio Camerani
    Sep 13 '10 at 12:15
  • 1
    $\begingroup$ As for the second answer, it is possible to compute K from K′ (and F); otherwise a mapping from F to F′ would not be a reduction. However, your question is about whether it is possible to make a reduction such that K=K′. The answer is that it is not possible. $\endgroup$
    – Tsuyoshi Ito
    Sep 13 '10 at 12:46
  • $\begingroup$ @Tsuyoshi Ito: A further comment on your second answer. Having the same number of solutions doesn't imply having the same solution space. An instance A may have the same number of solutions of an instance B, but B's solutions may be distributed in a completely different manner in the solution space. $\endgroup$
    – Giorgio Camerani
    Sep 13 '10 at 12:47
  • 1
    $\begingroup$ I do not know freely available copies of the papers I cited. A proof of the #P-completeness of Permanent is in many textbooks on computational complexity, which may be available at libraries: e.g. Computational Complexity by Papadimitriou, Computational Complexity: A Conceptual Perspective by Goldreich and Computational Complexity: A Modern Approach by Arora and Barak contain a proof. (more) $\endgroup$
    – Tsuyoshi Ito
    Sep 13 '10 at 15:46

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.