🔢 mathematics

CNFs and DNFs with Exactly $k$ Solutions

This article establishes new upper and lower bounds on the minimum number of terms or clauses required to construct a DNF or CNF formula with exactly $k$ satisfying assignments by demonstrating that a monotone DNF can be constructed with $O(\sqrt{\log k}\log\log k)$ terms while simultaneously showing that $\Omega(\log\log k)$ terms are necessary for certain values of $k$ .

Original authors: L. Sunil Chandran, Rishikesh Gajjala, Kuldeep S. Meel

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: L. Sunil Chandran, Rishikesh Gajjala, Kuldeep S. Meel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect trying to build a very specific type of "digital gate." This gate has a single mission: it must allow exactly $k$ distinct combinations of keys (solutions) to pass through and block every other combination.

In the world of computer science, these "gates" are called Boolean formulas. They are built with logical switches (variables) that can be either ON (True) or OFF (False).

CNF (Conjunctive Normal Form) is like a list of rules where all rules must be followed (an AND of ORs).
DNF (Disjunctive Normal Form) is like a list of scenarios where a single true scenario is sufficient (an OR of ANDs).

The big question this work poses is: What is the smallest, most efficient way to build a gate that allows exactly $k$ keys to pass?

If you simply throw random switches at the problem, you might end up with a huge, cumbersome machine with thousands of parts. The authors want to know: What is the absolute minimum number of parts (terms or clauses) required to obtain exactly $k$ solutions?

The Problem with "Simple Counting"

Previously, experts knew that such a gate could be built with approximately $\log(k)$ parts. Imagine this as building a house: if you need space for $k$ people, you might think you need a number of rooms proportional to the number of digits in $k$ .

The authors of this work say: "Wait, we can do much better." They have found a way to build these gates with significantly fewer parts, specifically around $\sqrt{\log k \times \log \log k}$ .

To put this in perspective:

If $k$ is a huge number (like a billion), the old method might suggest you need a few dozen parts.
The new method suggests you might need only a handful. It is a massive efficiency upgrade, shrinking the machine from a "large truck" to a "compact car."

The Secret Ingredient: "Block Counting"

How did they achieve this? They discovered a hidden pattern in the number $k$ itself. They introduced a concept called "block counting."

Imagine you write the number $k$ in the binary system (using only 1s and 0s).

Example: The number 49 in binary is 110001.
Instead of viewing it as a bit sequence, look at the groups (or "blocks") of consecutive 1s and 0s.
- 11 is a block of 1s.
- 000 is a block of 0s.
- 1 is a block of 1s.
The "block count" is simply the number of these groups. For 49, the block count is 3.

The authors found that the complexity of building your gate depends less on the size of the number $k$ and more on how "chunky" its binary representation is (its block count). If a number has a simple, chunky structure, you can build the gate very efficiently.

The Two Sides of the Coin

The work delivers two main results, like the two sides of a coin:

1. The Upper Bound (The "How-to" Guide):
They proved that for any number $k$ , you can always build a gate with exactly $k$ solutions using a very small number of parts. They used a clever construction method involving "splitting" and "lifting" (mathematical tricks to combine and scale smaller gates) to prove that the required number of parts is approximately the square root of the logarithm of $k$ .

Analogy: It is like realizing you don't need to build a new wall for every single brick; you can build a few modular walls and stack them in a specific pattern to create a wall of any desired height, using very little material.

2. The Lower Bound (The "Hard Truth"):
They also proved that for some numbers, you cannot do better than a certain limit. There are infinitely many numbers for which you absolutely need at least $\log \log k$ parts. You cannot shrink the gate down to a single switch for every number.

Analogy: No matter how clever you are, some numbers are simply "messy" in their binary representation, and you physically need a minimum amount of hardware to represent them.

Why Does This Matter?

This research is about efficiency. In the real world, computers often need to solve "model counting" problems—figuring out in how many ways a complex system can function (such as calculating the probability of a network failure or an interaction between a drug and a protein).

To do this, computers often convert complex problems into these "gates" (CNF/DNF formulas).

If the gate is huge (too many parts), it takes the computer forever to count the solutions.
If the gate is tiny (few parts), the computer solves it instantly.

By showing that we can build these gates much smaller than previously assumed, the authors have provided a new blueprint to make these calculations faster and more efficient.

Summary

The Goal: Build a logical gate that accepts exactly $k$ solutions.
The Old Way: You needed about $\log(k)$ parts.
The New Way: You often get by with about $\sqrt{\log k}$ parts.
The Trick: It depends on the "block structure" of the number $k$ in the binary system.
The Result: A much more efficient way to represent complex counting problems, helping computers solve difficult probability and verification tasks faster.

The authors conclude that while they have found a very efficient way to build these gates, there is still a tiny gap between the best possible method and the worst-case scenario they proved. They suspect the true answer lies somewhere in between, likely related to the "block counting" pattern they discovered.

Technical Conclusion: CNFs and DNFs with Exactly k Solutions

Problem Statement
The work addresses a fundamental question in the context of model counting and its weighted variant: What is the minimum number of terms (for Disjunctive Normal Form, DNF) or clauses (for Conjunctive Normal Form, CNF) required to construct a formula with exactly $k$ satisfying assignments? This quantity is denoted as $\beta(k)$ .

While it is known that $\beta(k) = O(\log k)$ , the authors investigate whether tighter bounds exist. The problem is motivated by the efficiency of reducing weighted model counting to unweighted model counting; a reduction is more efficient if the constructed auxiliary formula contains fewer terms or clauses. The authors observe that $\beta(k)$ is not monotonic; for instance, for $k = 2^q$ , it holds that $\beta(k) = 1$ , whereas for other values, significantly more terms may be required.

Methodology and Theoretical Framework
The core of the work's methodology lies in establishing a rigorous equivalence between the problem of finding DNFs with $k$ solutions of minimal size and the combinatorial theory of ideals of set systems.

Connection to Ideals of Set Systems:
The authors define a monotone DNF formula over variables $x_1, \dots, x_m$ as a family of subsets of $U = \{1, \dots, m\}$ . They prove that the set of satisfying assignments of a monotone DNF corresponds bijectively to the order ideal (down-set) generated by the family of subsets assigned to the terms of the DNF. Consequently, finding the minimum number of terms for a DNF with $k$ solutions is equivalent to finding the minimum size of a family of sets $S$ such that the cardinality of the ideal generated by $S$ , denoted as $|ID(S)|$, equals $k$ . This minimum size is defined as $\alpha(k)$ . The work notes that $\alpha(k) \ge \beta(k)$ holds.
Block-Count Parameter:
To analyze $\alpha(k)$ , the authors introduce the block count of a number, $bl(k)$. This is derived from the "block binary representation" of $k$ , where consecutive blocks of 1s and 0s in the bit sequence are grouped. For example, $49 $($ 110001_2$) is represented as $1^2 0^3 1^1$ , yielding $bl(49) = 3$.
Combinatorial Operations:
The construction of upper bounds relies on two fundamental operations on set families:
- Splitting: A lemma showing that $\alpha(m+k) \le \alpha(m) + \alpha(k+1)$ . This enables the decomposition of the construction of large ideals into smaller ones.
- Lifting: A lemma showing that $\alpha(2^t \cdot k) \le \alpha(k)$ . This allows scaling the size of an ideal by a power of 2 without increasing the number of generators by adding new disjoint elements to the generator sets.

Main Contributions and Results

Lower Bound:
The work proves that for every $k$ : $\log(bl(k) + 1) \le \beta(k)$ . Furthermore, it is shown that there are infinitely many values for $k$ for which every DNF or CNF representation requires at least $\Omega(\log \log k)$ terms or clauses. This demonstrates that the complexity of representing $k$ solutions is inherently linked to the block structure of $k$ .
Upper Bound (Main Result):
The primary contribution is the construction of a monotone DNF with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k \log \log k})$ terms.
- The authors prove that for every $k \ge 3$ : $\beta(k) \le \min \{ O(\sqrt{\log k \log \log k}), bl(k) + 1 \}$ .
- This result represents the first upper bound of $o(\log k)$ for this problem and significantly improves the previously known bound of $O(\log k)$ .
- The construction involves a sophisticated decomposition of $k$ based on its binary structure using the splitting and lifting lemmas to generate ideals of specific cardinalities. In particular, for numbers of the form $2^{3q^2} + \beta$ , the authors construct a family of sets of size $O(q \log q)$ (where $q \approx \sqrt{\log k}$ ) that generates an ideal of the required size.

Significance and Claims
The work claims that these results have significant implications for the efficiency of model counting algorithms based on formula transformations. By reducing the number of terms required to encode a specific number of solutions, the reduction from weighted to unweighted model counting becomes more efficient.

The authors explicitly state that their construction provides the first sub-logarithmic ( $o(\log k)$ ) bound for the problem. They further formulate the conjecture that $\beta(k)$ is a polynomial in $\log(bl(k) + 1)$ , suggesting that the block count is the precise structural parameter determining the compactness of such formulas.

The work connects model counting with extremal set theory, specifically the study of ideals and antichains, and potentially opens pathways for applying these combinatorial techniques to other problems regarding the expressiveness and compactness of representations of Boolean functions. The work does not claim to close the gap between the lower bound of $\Omega(\log \log k)$ and the upper bound of $O(\sqrt{\log k \log \log k})$ , but identifies this as an open problem for future research.