Small Unsatisfiable k-CNFs with Bounded Literal Occurrence

Tianwei Zhang, Tomás Peitl, Stefan Szeider

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.

Figure 2: Bipartite graph and its corresponding adjacency matrix representation used in the SMS framework to represent CNF formulas.

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.

Figure 5: Tables showing the minimum number of clauses μ for various (3, s) and (3, p, q) configurations, establishing exact bounds for small k-CNFs.

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

BibTeX
@inproceedings{zhang2024small,
  author = {Tianwei Zhang and Tomás Peitl and Stefan Szeider},
  title = {{Small Unsatisfiable k-CNFs with Bounded Literal Occurrence}},
  booktitle = {SAT},
  year = {2024},
  doi = {10.4230/lipics.sat.2024.31},
}
Figure