8
$\begingroup$

Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by counting reduction.

Suppose $f,g : \{0,1\}^* \to \mathbb N$ are two counting problems. For example, #SAT asks how many satisfiable assignments are there for a specific instance $\phi$, and $f,g$ are similar counting problems finding total number of witnesses. A weakly parsimonious counting reduction from $f$ to $g$ consists of a pair of polynomial time computable functions $\sigma : \{0,1\}^* \to \{0,1\}^*$ and $\tau : \{0,1\}^* \times \mathbb N \to \mathbb N$ such that $f(x) = \tau (x, g(\sigma(x)))$. In the case that $f(x) = g(\sigma(x))$, this is known as strongly parsimonious counting reduction.

I can see that if there is any such counting reduction from #SAT to #HornSAT, it must be weakly parsimonious reduction: a strong reduction would imply that the #SAT and #HornSAT instances will have zero or non-zero number of solutions together, and assuming that $\mathsf P \ne \mathsf{NP}$, this is impossible (as HornSAT $\in \mathsf P$ while SAT is $\mathsf{NP}$-complete).

So my question is: is there any weakly parsimonious counting reduction from #SAT to #HornSAT? If so, can anyone please give me some reference ?

$\endgroup$
  • 2
    $\begingroup$ “#HornSAT is #P-complete” means that every #P problem can be reduced to #HornSAT by a counting (weakly parsimonious) reduction. $\endgroup$ – Tsuyoshi Ito Sep 26 '12 at 18:29
  • 1
    $\begingroup$ What does weakly vs. strongly parsimonious mean? $\endgroup$ – Huck Bennett Sep 26 '12 at 18:32
  • $\begingroup$ @Huck Bennett... I have mentioned the mathematical definition in the question. Informally we can say, strong reduction means both the problems have same number of solutions. Weak reduction means number of solutions of the original problem instance can be found in polynomial time from the number of solutions of the reduced problem instance. $\endgroup$ – David Sep 26 '12 at 18:40
  • $\begingroup$ @TsuyoshiIto.. right, it means there must be a counting (weakly parsimonious) reduction from #SAT to #HornSAT. I want to know that reduction. I haven't found any direct or indirect reduction. Basically I don't know how to prove “#HornSAT is #P-complete”. May be I'm not that good in google search. Any reference ?? $\endgroup$ – David Sep 26 '12 at 18:43
10
$\begingroup$

This post discusses #P-completeness of #Monotone-2SAT under weakly parsimonious reductions. If you negate all literals in a monotone 2-CNF formula $\phi$, you obtain a Horn 2-CNF formula $\psi$ with the same number of satisfying assignments.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much for the pointer. It really helps me a lot. :) $\endgroup$ – David Sep 27 '12 at 10:01

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.