What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically the same modulo repeated clauses. Thus $$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor x_1\lor \lnot x_1)$$ are the same while $$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor \lnot x_1\lor x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones? If the exact numbers cannot be given, just some recurrence formulas will do. Does the $\lim$ of the fraction of satisfiable ones go to $0$ as $n\to \infty$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Marginally related: in arxiv.org/pdf/0808.0739.pdf, we showed that the set of satisfiable formula in $\ell$-CNF in $n$ variables is homotopy equivalent to the Alexander dual of the hypergraph of $\ell$-faces of the $n$-cube. $\endgroup$– Jim ConantCommented Aug 20, 2022 at 17:53
-
$\begingroup$ Name of @JimConant's reference: Conant and Thistlethwaite - Boolean formulae, hypergraphs and combinatorial topology. $\endgroup$– LSpiceCommented Aug 20, 2022 at 18:23
-
$\begingroup$ Your equivalence seems very mild. For example, same collection of clauses in different order = different formula? In a clause, same literals in different order = different clause? So in essence, from all $(2n)^3$ possible clauses, take any subset of any size in any order? $\endgroup$– Jukka KohonenCommented Feb 9, 2023 at 9:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Regarding the fraction of satisfiable 3-CNF formulas in $n$ variables, it is widely believed that there is a phase transition that occurs depending on how many clauses there are compared to the number of variables. To be precise, it is conjectured (but not yet proven) that if there are more than $\alpha n$ clauses, then the formula is almost surely unsatisfiable, and if there are less than $\alpha n$ clauses then the formula is almost surely satisfiable (where $\alpha$ is around 4.2667). This phase transition has been established for $k$-SAT when $k$ is large. See Proof of the satisfiability conjecture for large $k$ by Ding, Sly, and Sun.
answered Aug 20, 2022 at 18:09
-
$\begingroup$ Must the clauses in $\alpha n$ do be distinct, in what sense, in the one from my OQ ? $\endgroup$ Commented Aug 21, 2022 at 11:33
-
$\begingroup$ Also, could you explain to me what means "formula is almost surely satisfiable" in this context ? $\endgroup$ Commented Aug 22, 2022 at 15:55
-
$\begingroup$ @user1642683 It means that for any fixed $\beta<\alpha$, the limit of the fraction of satisfiable formulas among random $3$-CNF with $n$ variables and $\le\beta n$ clauses as $n\to\infty$ is $1$. $\endgroup$ Commented Feb 9, 2023 at 7:39
-
$\begingroup$ I should have written $\beta n$ rather than $\le\beta n$ (but this proably does not make a difference). $\endgroup$ Commented Feb 9, 2023 at 8:04