<p><a href="https://cstheory.stackexchange.com/questions/1247/reducing-sat-to-monotone-2sat">This post</a> discusses #P-completeness of #Monotone-2SAT under weakly parsimonious reductions. If you negate <em>all</em> literals in a monotone 2-CNF formula $\phi$, you obtain a Horn 2-CNF formula $\psi$ with the same number of satisfying assignments.</p>

CC BY-SA 3.0
2012-09-27T10:01:28.510Z
Thank you very much for the pointer. It really helps me a lot. :)
David
CC BY-SA 3.0
2012-09-26T23:46:45.937Z
2012-09-26T23:46:45.937Z
2017-04-13T12:32:28.167Z
Radu Curticapean
<p>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. </p>

<p>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 <em>weakly parsimonious counting reduction</em> 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.</p>

<p>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).</p>

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

CC BY-SA 3.0
2012-09-26T18:29:08.267Z
“#HornSAT is #P-complete” _means_ that every #P problem can be reduced to #HornSAT by a counting (weakly parsimonious) reduction.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-26T18:32:12.910Z
What does weakly vs. strongly parsimonious mean?
Huck Bennett
CC BY-SA 3.0
2012-09-26T18:40:10.703Z
@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.
David
CC BY-SA 3.0
2012-09-26T18:43:07.780Z
@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 ??
David
<cc.complexity-theory><complexity-classes><sat><counting-complexity><reductions>
Counting reduction from #SAT to #HornSAT?
David
# Counting reduction from #SAT to #HornSAT?

(Asked by: username_0 on 2012-09-26)

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 ?

**Tags:** cc.complexity-theory, complexity-classes, sat, counting-complexity, reductions
> **Comments:**
> **username_1**: “#HornSAT is #P-complete” _means_ that every #P problem can be reduced to #HornSAT by a counting (weakly parsimonious) reduction.  
> **username_2**: What does weakly vs. strongly parsimonious mean?  
> **username_0**: @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.  
> **username_0**: @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 ??  

---

## 1 answers

### Answer by username_3 on 2012-09-26. Score: 11 | Accepted answer

[This post](https://cstheory.stackexchange.com/questions/1247/reducing-sat-to-monotone-2sat) 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.

> **Comments:**
> **username_0**: Thank you very much for the pointer. It really helps me a lot. :)  

---

