I'm looking for some published results, either empirical or theoretical, on the number of solutions to random 3-SAT problems. Given $N$ variables and a clause-to-variable ratio $\alpha$, how does the number of solutions to 3-SAT scale vs. $N$ and $\alpha$? What is the distribution of the number of solutions?


  • $\begingroup$ Regarding your first question, you can start with the Nature article cacs.usc.edu/education/cs653/Mezard-RSAT-Science02.pdf and its complete version lptms.u-psud.fr/ressources/publis/2002/…. I have seen relevant lecture notes, but unfortunately cannot find them at the moment. $\endgroup$ – Yuval Filmus Feb 28 '16 at 22:43
  • 1
    $\begingroup$ I suggest you edit your question to make it self-contained and define all notation (what do $N$ and $\alpha$ represent)? $\endgroup$ – D.W. Feb 29 '16 at 7:11
  • $\begingroup$ $N$ is the number of variables, $\alpha$ is the clause density (there are $\alpha N$ clauses). $\endgroup$ – Yuval Filmus Feb 29 '16 at 8:19
  • $\begingroup$ You are asking two different questions. Usually the rule is one question per post. $\endgroup$ – Yuval Filmus Feb 29 '16 at 8:19

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.