<p>Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.</p>

<p>We know that in the worst case, it is #P-complete, but what can we say about an average instance of #SAT?</p>

CC BY-SA 4.0
2020-01-31T08:04:31.490Z
Over what distribution of instances?
D.W.
CC BY-SA 4.0
2020-01-31T14:19:35.927Z
It's not enough to say "uniform distribution".  Over what set of instances?  Note that whether a random formula is likely to be satisfiable *at all* depends on how the number of clauses relates to the number of variables. Search scholar.google.com for, e.g., "random SAT threshold".  https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=random+SAT+threshold&btnG=
Neal Young
CC BY-SA 4.0
2020-01-31T14:25:21.487Z
FWIW, some variants of computing the *Permanent* of a given matrix are known to be both #P-complete, and as hard in the average case as the worst case.
Neal Young
<counting-complexity><average-case-complexity>
Average case hardness of #SAT
arika
# Average case hardness of #SAT

(Asked by: username_0 on 2020-01-30)

Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.

We know that in the worst case, it is #P-complete, but what can we say about an average instance of #SAT?

**Tags:** counting-complexity, average-case-complexity
> **Comments:**
> **username_1**: Over what distribution of instances?  
> **username_2**: It's not enough to say "uniform distribution".  Over what set of instances?  Note that whether a random formula is likely to be satisfiable *at all* depends on how the number of clauses relates to the number of variables. Search scholar.google.com for, e.g., "random SAT threshold".  https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=random+SAT+threshold&btnG=  
> **username_2**: FWIW, some variants of computing the *Permanent* of a given matrix are known to be both #P-complete, and as hard in the average case as the worst case.  

---

## 0 answers

