Introduction
In Boolean satisfiability (SAT), a $(k, s)$-formula is a Conjunctive Normal Form (CNF) where every clause contains exactly $k$ literals and each variable appears in at most $s$ clauses. A fundamental result in computer science is the existence of a threshold $f(k)$: if $s \le f(k)$, the formula is always satisfiable; if $s > f(k)$, the problem of determining satisfiability becomes NP-complete. For instance, it is known that $f(3)=3$ and $f(4)=4$.
A significant open question in extremal combinatorics is determining the size of the smallest possible unsatisfiable formula for given parameters $k$ and $s$. These minimal counterexamples are not merely mathematical curiosities; they serve as essential building blocks for proving inapproximability bounds for MaxSAT. Researchers from TU Wien have recently determined exact sizes for several classes of 3-CNF and 4-CNF formulas, pushing the boundaries of what is known about these structures.
Methodology: SAT Modulo Symmetries
The researchers employed a hybrid approach combining combinatorial theory with advanced computational search. The primary tool was a SAT Modulo Symmetries (SMS) framework. This framework generates graphs representing formulas while automatically pruning isomorphic copies, drastically reducing the search space by preventing the solver from re-evaluating renamed versions of previously checked formulas.
Graph Encoding and Matrix Optimization
CNF formulas were represented as bipartite "clause-literal" graphs. To further optimize the search, the team proved a specific theorem (Theorem 1) showing that the adjacency matrix of a minimal formula must possess a fixed "antidiagonal" structure in its upper-left block. This theoretical insight allowed them to hard-code parts of the search space, significantly reducing the number of undecided variables the SAT solver had to process.
Beyond standard $(k, s)$ constraints, the study explored $(k, p, q)$ formulas, where $p$ and $q$ denote the maximum positive and negative occurrences of a variable, respectively. This granular approach led to a new Dichotomy Theorem for (3, 1, $q$)-SAT, proving it is solvable in polynomial time if $p+q < 4$ and NP-hard otherwise.
Key Results and Improvements
The study successfully determined the exact minimum number of clauses, denoted as $\mu(k, s)$, for several 3-CNF configurations and established new records for 4-CNF.
Significant findings include:
- Exact 3-CNF Sizes: The minimum clause counts were found to be $\mu(3, 4) = 16$, $\mu(3, 5) = 11$, and $\mu(3, 6) = 8$.
- Breaking the (4, 5) Record: By utilizing a modified saturation algorithm to find better "axioms" for disjunctive splitting, the researchers reduced the upper bound for the smallest unsatisfiable (4, 5)-CNF from 257 to 235 clauses. This improvement notably outperformed previous state-of-the-art constructions by Donald Knuth.
- Enforcer Characterization: The team provided the first exact sizes for smallest (3, $s$)-enforcers—satisfiable formulas that force a specific variable assignment—such as 5 clauses for $s=4$.
Conclusion and Future Directions
While the methods proved highly effective for $k=3$ and $k=4$, scaling to $k=5$ remains a challenge due to the exponential growth of the search space; the threshold $f(5)$ is currently only known to lie between 5 and 7. Future work will focus on further theoretical breakthroughs to "hard-code" more complex formula structures into the SMS framework. Additionally, these new minimal formulas are expected to provide the foundation for deriving stronger inapproximability bounds for MaxSAT solvers.
Summary updated