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?
$\begingroup$
$\endgroup$
-
3$\begingroup$ Over what distribution of instances? $\endgroup$ – D.W. Jan 31 '20 at 8:04
-
2$\begingroup$ 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". scholar.google.com/… $\endgroup$ – Neal Young Jan 31 '20 at 14:19
-
2$\begingroup$ 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. $\endgroup$ – Neal Young Jan 31 '20 at 14:25
