Bollobás–Brightwell–Leader conjecture on enumerating k-SAT functions

Let k2k\geq 2 be fixed. A kk-SAT function on nn boolean variables is a Boolean function represented by a formula whose clauses have size kk, and it is unate if it is monotone after replacing some variables with their negations.

Bollobás–Brightwell–Leader conjecture. The number of kk-SAT functions on nn boolean variables is

(1+o(1))2n+(nk).(1+o(1))2^{n+\binom{n}{k}}.

Equivalently, a 1o(1)1-o(1) fraction of all kk-SAT functions on nn variables are unate.

This conjecture gives the asymptotically sharp count suggested by unate functions. It was proved for k=2k=2 and k=3k=3, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.