How many k-SAT functions on n boolean variables are there?
Statement
How many k-SAT functions on n boolean variables are there? What does a typical such function look like? Enumerating k-SAT functions Yufei Zhao (joint work with Dingding Dong and Nitya Mani) Conjecture 1 (Bollobás, Brightwell, and Leader [3]). Fix k ě 2. The number of n k-SAT functions on n boolean variables is p1 op1qq2npk q . Equivalently: a 1´op1q fraction of all k-SAT functions on n variables are unate.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.