pith. sign in

arxiv: 1005.2861 · v1 · submitted 2010-05-12 · 🧮 math.CO

The number of 3-SAT functions

classification 🧮 math.CO
keywords binomfunctionsnumberasymptoticbollobbooleanbrightwellcase
0
0 comments X
read the original 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+\binom{n}{3}}$. This is a strong form of the case $k=3$ of a conjecture of Bollob\'as, Brightwell and Leader stating that for fixed $k$, $\log_2 G_k(n)\sim \binom{n}{k}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.