<p>Also, #SAT does not have fully polynomial randomized approximation scheme (FPRAS)
unless $NP=RP$.</p>

CC BY-SA 3.0
2013-09-26T22:39:02.163Z
@SadeqDousti The reference is David Zuckerman, _On unapproximable versions of NP-complete problems_, SIAM Journal on Computing 25(6):1293-1304, 1996. Links: [DOI](http://dx.doi.org/10.1137/S0097539794266407), [author's homepage](http://www.cs.utexas.edu/~diz/pubs/approx.ps).  In fact, he proves the stronger result that you can't even approximate the logarithm of the number of solutions unless NP=RP.
David Richerby
CC BY-SA 3.0
2013-09-27T10:58:27.263Z
@DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D
Sadeq Dousti
CC BY-SA 2.5
2010-09-09T12:30:07.050Z
Could you provide a reference?
Sadeq Dousti
CC BY-SA 2.5
2010-09-09T14:15:28.493Z
Intuitively, an FRPAS will allow you to distinguish the case of zero solutions and non-zero solutions, which is the NP-complete problem SAT.
Robin Kothari
CC BY-SA 2.5
2010-09-07T16:47:19.327Z
2010-09-07T16:47:19.327Z
Mohammad Al-Turkistany
<p>To my knowledge, no one has figured out how to exploit the &quot;counting solutions&quot; property of #SAT in any lower bound on deterministic algorithms, so unfortunately the best known lower bounds for #SAT are basically the same as that for SAT.</p>
<p>However, there has been a little progress. Note that the decision version of #SAT is called &quot;Majority-SAT&quot;: <em>given a formula, do at least <span class="math-container">$1/2$</span> of the possible assignments satisfy it?</em> &quot;Majority-SAT&quot; is <span class="math-container">$PP$</span>-complete, and given an algorithm for Majority-SAT, one can solve #SAT with <span class="math-container">$O(n)$</span> calls to the algorithm.</p>
<p>The closest that people have gotten to new lower bounds for #SAT (that are not known to hold for SAT) is with lower bounds for &quot;Majority-of-Majority-SAT&quot;: <em>given a propositional formula over two sets of variables X and Y, for at least <span class="math-container">$1/2$</span> of the possible assignments to <span class="math-container">$X$</span>, is it true that at least <span class="math-container">$1/2$</span> of the assignments to <span class="math-container">$Y$</span> make the formula satisfiable?</em> This problem is in the &quot;second level&quot; of the counting hierarchy (the class <span class="math-container">$PP^{PP}$</span>). Quantum time-space lower bounds (and more) are known for this class.</p>
<p>The survey at <a href="http://pages.cs.wisc.edu/%7Edieter/Papers/sat-lb-survey-fttcs.pdf" rel="noreferrer">http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf</a> gives an overview of results in this direction.</p>
<p><strong>UPDATE: As of 2019, the first paragraph in the above is obsolete. It is known that #SAT requires a time-space product that is basically <span class="math-container">$n^2$</span>. See for example</strong>
&quot;Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle&quot; <a href="https://drops.dagstuhl.de/opus/volltexte/2018/10149/" rel="noreferrer">https://drops.dagstuhl.de/opus/volltexte/2018/10149/</a></p>

CC BY-SA 2.5
2010-09-08T08:40:16.407Z
Thanks for your useful answer. Thanks also for the pointer to the survey.
Giorgio Camerani
CC BY-SA 4.0
2010-09-07T16:36:28.930Z
2021-02-19T01:45:15.227Z
2021-02-19T01:45:15.227Z
Ryan Williams
<p>The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on #SAT?</p>

<cc.complexity-theory><lower-bounds><sat><counting-complexity>
Lower bounds on #SAT?
Giorgio Camerani
# Lower bounds on #SAT?

(Asked by: username_0 on 2010-09-07)

The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on #SAT?

**Tags:** cc.complexity-theory, lower-bounds, sat, counting-complexity

---

## 2 answers

### Answer by username_5 on 2010-09-07. Score: 32 | Accepted answer

To my knowledge, no one has figured out how to exploit the "counting solutions" property of #SAT in any lower bound on deterministic algorithms, so unfortunately the best known lower bounds for #SAT are basically the same as that for SAT.

However, there has been a little progress. Note that the decision version of #SAT is called "Majority-SAT": *given a formula, do at least $1/2$ of the possible assignments satisfy it?* "Majority-SAT" is $PP$-complete, and given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm.

The closest that people have gotten to new lower bounds for #SAT (that are not known to hold for SAT) is with lower bounds for "Majority-of-Majority-SAT": *given a propositional formula over two sets of variables X and Y, for at least $1/2$ of the possible assignments to $X$, is it true that at least $1/2$ of the assignments to $Y$ make the formula satisfiable?* This problem is in the "second level" of the counting hierarchy (the class $PP^{PP}$). Quantum time-space lower bounds (and more) are known for this class.

The survey at [http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf](http://pages.cs.wisc.edu/%7Edieter/Papers/sat-lb-survey-fttcs.pdf) gives an overview of results in this direction.

**UPDATE: As of 2019, the first paragraph in the above is obsolete. It is known that #SAT requires a time-space product that is basically $n^2$. See for example**
"Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle" <https://drops.dagstuhl.de/opus/volltexte/2018/10149/>

> **Comments:**
> **username_0**: Thanks for your useful answer. Thanks also for the pointer to the survey.  

---

### Answer by username_1 on 2010-09-07. Score: 7

Also, #SAT does not have fully polynomial randomized approximation scheme (FPRAS)
unless $NP=RP$.

> **Comments:**
> **username_3**: Could you provide a reference?  
> **username_4**: Intuitively, an FRPAS will allow you to distinguish the case of zero solutions and non-zero solutions, which is the NP-complete problem SAT.  
> **username_2**: @SadeqDousti The reference is David Zuckerman, _On unapproximable versions of NP-complete problems_, SIAM Journal on Computing 25(6):1293-1304, 1996. Links: [DOI](http://dx.doi.org/10.1137/S0097539794266407), [author's homepage](http://www.cs.utexas.edu/~diz/pubs/approx.ps).  In fact, he proves the stronger result that you can't even approximate the logarithm of the number of solutions unless NP=RP.  
> **username_3**: @DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D  

---

