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
-
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 YoungJan 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 YoungJan 31 '20 at 14:25
Add a comment
|