9
$\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 ?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ “#HornSAT is #P-complete” means that every #P problem can be reduced to #HornSAT by a counting (weakly parsimonious) reduction. $\endgroup$
    – Tsuyoshi Ito
    Commented Sep 26, 2012 at 18:29
  • 1
    $\begingroup$ What does weakly vs. strongly parsimonious mean? $\endgroup$
    – Huck Bennett
    Commented Sep 26, 2012 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
    Commented Sep 26, 2012 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
    Commented Sep 26, 2012 at 18:43

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for the pointer. It really helps me a lot. :) $\endgroup$
    – David
    Commented Sep 27, 2012 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.