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?

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.