The number of 3-SAT functions

Abstract

With $G_k(n)$ the number of functions of $n$ boolean variables definable by $k$-SAT formulae, we prove that $G_3(n)$ is asymptotic to $2^{n+\left(\genfrac{}{}{0ex}{}{n}{3}\right)}$. This is a strong form of the case $k=3$ of a conjecture of Bollobás, Brightwell and Leader stating that for fixed $k$, ${\log }_2{G}_k(n)\sim \left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

51 pages

References in corpus (2)

• Hypergraph regularity and the multidimensional Szemerédi theorem
• On the Number of 2-SAT Functions