Bollobás–Brightwell–Leader conjecture on enumerating k-SAT functions
Bollobás–Brightwell–Leader conjecture on enumerating k-SAT functions
Let be fixed. A -SAT function on boolean variables is a Boolean function represented by a formula whose clauses have size , and it is unate if it is monotone after replacing some variables with their negations.
Bollobás–Brightwell–Leader conjecture. The number of -SAT functions on boolean variables is
Equivalently, a fraction of all -SAT functions on variables are unate.
This conjecture gives the asymptotically sharp count suggested by unate functions. It was proved for and , while the general case remains open.
Sources & referencesView supporting material
Primary source
Dingding Dong, Nitya Mani and Yufei Zhao, “Enumerating k-SAT functions”, arXiv:2107.09233 (2022).
Additional references
3 papers in this index state this conjecture (2010–2021). The statement above is taken from the most recent of them; the others are arXiv:1005.2861, arXiv:1005.2863.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.