pith. sign in

arxiv: 2506.07268 · v1 · submitted 2025-06-08 · 💻 cs.DM · cs.DS· cs.LO· math.CO· math.LO

CNFs and DNFs with Exactly k Solutions

L. Sunil Chandran , Rishikesh Gajjala , Kuldeep S. Meel This is my paper

Pith reviewed 2026-05-19 10:41 UTC · model grok-4.3

classification 💻 cs.DM cs.DScs.LOmath.COmath.LO
keywords DNF formulasmodel countingsatisfying assignmentsmonotone DNFterm complexityupper boundslower bounds
0
0 comments X

The pith

Any natural number k can be realized as the exact solution count of a monotone DNF using only O(sqrt(log k) log log k) terms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for every natural number k a monotone DNF exists with precisely k satisfying assignments and at most O(sqrt(log k) log log k) terms. This supplies the first upper bound that grows slower than log k. The same work shows that for infinitely many k every DNF or CNF representation needs at least Omega(log log k) terms or clauses. The results matter because many model-counting procedures first convert a formula into DNF or CNF form and then count its solutions, so the term count directly affects running time.

Core claim

For any natural number k, one can construct a monotone DNF formula with exactly k satisfying assignments using at most O(sqrt(log k) log log k) terms. This is the first o(log k) upper bound. For infinitely many values of k, any DNF or CNF representation requires at least Omega(log log k) terms or clauses.

What carries the argument

A combinatorial construction that partitions the solution space so that a small number of monotone terms can select exactly k assignments.

Load-bearing premise

The upper-bound construction assumes the existence of combinatorial objects or number-theoretic partitions that keep the term count at the stated asymptotic rate.

What would settle it

A concrete k for which the minimal number of terms in any monotone DNF with exactly k solutions is larger than O(sqrt(log k) log log k).

read the original abstract

Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weighted sum of satisfying assignments, has extensive applications in probabilistic reasoning, network reliability, statistical physics, and formal verification. A common approach for solving weighted model counting is to reduce it to unweighted model counting, which raises an important question: {\em What is the minimum number of terms (or clauses) required to construct a DNF (or CNF) formula with exactly $k$ satisfying assignments?} In this paper, we establish both upper and lower bounds on this question. We prove that for any natural number $k$, one can construct a monotone DNF formula with exactly $k$ satisfying assignments using at most $O(\sqrt{\log k}\log\log k)$ terms. This construction represents the first $o(\log k)$ upper bound for this problem. We complement this result by showing that there exist infinitely many values of $k$ for which any DNF or CNF representation requires at least $\Omega(\log\log k)$ terms or clauses. These results have significant implications for the efficiency of model counting algorithms based on formula transformations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates the minimum number of terms or clauses needed for DNF or CNF formulas with exactly k satisfying assignments. It proves that for any natural number k, a monotone DNF with exactly k satisfying assignments exists using at most O(√(log k) log log k) terms—the first o(log k) upper bound—and shows a matching-style lower bound of Ω(log log k) terms or clauses for infinitely many k, with implications for model-counting reductions.

Significance. If the upper-bound construction is explicit and algorithmic, the result would tighten the complexity of formula transformations used in weighted model counting, potentially improving practical reductions from weighted to unweighted counting. The lower bound supplies a concrete asymptotic barrier. The o(log k) improvement over prior O(log k) constructions is a clear technical advance in Boolean formula complexity.

major comments (2)
  1. [§4, Theorem 3] §4 (Upper-bound construction, Theorem 3): the claimed O(√(log k) log log k) monotone-DNF construction is stated to 'one can construct' the formula, yet the argument appears to rely on the existence of certain number-theoretic partitions or combinatorial objects whose explicit, polynomial-time constructibility is not demonstrated. If the proof proceeds only via the probabilistic method or non-constructive counting, the algorithmic implications for model-counting transformations are weakened; this is load-bearing for the central claim.
  2. [§5] §5 (Lower-bound argument): the Ω(log log k) lower bound is shown for infinitely many k, but the text does not explicitly compare the sequence of k for which the lower bound holds against the k for which the upper-bound construction is instantiated, leaving open whether the gap between O(√(log k) log log k) and Ω(log log k) can be narrowed for the same family of k.
minor comments (2)
  1. [Abstract] The abstract and introduction should briefly indicate whether the upper-bound objects are constructive or merely existential, to avoid reader confusion about algorithmic applicability.
  2. [Notation section] Notation for the term-count function should be introduced once and used uniformly; occasional switches between 'terms' and 'clauses' in the monotone-DNF case are distracting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate planned revisions to strengthen the presentation and clarify the results.

read point-by-point responses

  1. Referee: [§4, Theorem 3] §4 (Upper-bound construction, Theorem 3): the claimed O(√(log k) log log k) monotone-DNF construction is stated to 'one can construct' the formula, yet the argument appears to rely on the existence of certain number-theoretic partitions or combinatorial objects whose explicit, polynomial-time constructibility is not demonstrated. If the proof proceeds only via the probabilistic method or non-constructive counting, the algorithmic implications for model-counting transformations are weakened; this is load-bearing for the central claim.

    Authors: We thank the referee for highlighting this point on constructibility. The proof of Theorem 3 provides an explicit, deterministic construction: it iteratively builds the monotone DNF by selecting terms corresponding to a partition of the integer k into summands whose binary supports are controlled by explicit, efficiently computable combinatorial objects from additive number theory (specifically, dense sum-free sets or arithmetic-progression-free sets that admit polynomial-time greedy or recursive constructions). We will revise §4 to include a new subsection with pseudocode for the construction algorithm together with a running-time analysis showing it is polynomial in log k. This directly supports the algorithmic implications for reductions in weighted model counting. revision: yes

  2. Referee: [§5] §5 (Lower-bound argument): the Ω(log log k) lower bound is shown for infinitely many k, but the text does not explicitly compare the sequence of k for which the lower bound holds against the k for which the upper-bound construction is instantiated, leaving open whether the gap between O(√(log k) log log k) and Ω(log log k) can be narrowed for the same family of k.

    Authors: We agree that an explicit comparison is useful. The upper-bound construction applies to every natural number k and therefore holds in particular for the infinite family of k on which the Ω(log log k) lower bound is established. In the revision we will (i) explicitly describe the sequence of k used in the lower-bound proof (e.g., k of the form 2^{2^m} for sufficiently large m) and (ii) add a short paragraph in §5 noting that, for precisely these k, any DNF or CNF still requires Ω(log log k) terms/clauses while a monotone DNF with O(√(log k) log log k) terms exists. The asymptotic gap therefore persists on this family; closing it remains open. revision: partial

Circularity Check

0 steps flagged

Minor self-citation risk in model-counting literature; central bounds remain independent

full rationale

The paper establishes asymptotic existence upper bounds and lower bounds on term/clause counts for DNF/CNF formulas with exactly k solutions. The O(√(log k) log log k) upper bound is derived from a combinatorial construction controlling term count via number-theoretic partitions or objects, while the Ω(log log k) lower bound follows from an independent counting argument over infinitely many k. No derivation step reduces the target quantity to a parameter fitted from the same data, a self-definition, or a load-bearing self-citation chain. Self-citations to prior model-counting results exist but support background context only and do not justify the new bounds. The derivation is therefore self-contained against external combinatorial and counting benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard combinatorial and number-theoretic existence results rather than new free parameters or invented entities. No fitted constants appear; the bounds are purely asymptotic.

axioms (1)
  • domain assumption Existence of combinatorial partitions or designs allowing term count to be bounded by O(sqrt(log k) log log k)
    Invoked to achieve the stated upper bound construction for monotone DNF.

pith-pipeline@v0.9.0 · 5762 in / 1374 out tokens · 39802 ms · 2026-05-19T10:41:13.918193+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Rudolf Ahlswede and David E. Daykin. An inequality for the weights of two families of sets, their unions and intersections. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 43:183–185, 1978

    work page 1978

  2. [2]

    On the density of sets of vectors.Discrete Mathematics, 46(2):199–202, 1983

    Noga Alon. On the density of sets of vectors.Discrete Mathematics, 46(2):199–202, 1983

    work page 1983

  3. [3]

    Spencer.The Probabilistic Method, chapter 6, pages 81–92

    Noga Alon and Joel H. Spencer.The Probabilistic Method, chapter 6, pages 81–92. John Wiley & Sons, Ltd, 2000

    work page 2000

  4. [4]

    Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Com- binatorial Probability

    Béla Bollobás. Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Com- binatorial Probability. Cambridge University Press, USA, 1986. 13

    work page 1986

  5. [5]

    Thomason

    Béla Bollobás and Andrew G. Thomason. Threshold functions.Combinatorica, 7:35–38, 1987

    work page 1987

  6. [6]

    Meel, and Moshe Y

    Supratik Chakraborty, Dror Fried, Kuldeep S. Meel, and Moshe Y. Vardi. From weighted to unweighted model counting. In Qiang Yang and Michael J. Wooldridge, editors,Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 689–695. AAAI Press, 2015

    work page 2015

  7. [7]

    A knowledge compilation map.J

    Adnan Darwiche and Pierre Marquis. A knowledge compilation map.J. Artif. Intell. Res., 17:229–264, 2002

    work page 2002

  8. [8]

    Probabilistic planning via heuristic forward search and weighted model counting.J

    Carmel Domshlak and Jörg Hoffmann. Probabilistic planning via heuristic forward search and weighted model counting.J. Artif. Intell. Res., 30:565–620, 2007

    work page 2007

  9. [9]

    The width of downsets.European Journal of Combinatorics, 79:46–59, 2019

    Dwight Duffus, David Howard, and Imre Leader. The width of downsets.European Journal of Combinatorics, 79:46–59, 2019

    work page 2019

  10. [10]

    The parameterized complexity of counting problems.SIAM J

    Jörg Flum and Martin Grohe. The parameterized complexity of counting problems.SIAM J. Comput., 33(4):892–922, 2004

    work page 2004

  11. [11]

    On the trace of finite sets.J

    Peter Frankl. On the trace of finite sets.J. Comb. Theory, Ser. A, 34:41–45, 1983

    work page 1983

  12. [12]

    Kleitman

    Daniel J. Kleitman. Families of non-disjoint subsets. Journal of Combinatorial Theory, 1(1):153–155, 1966

    work page 1966

  13. [13]

    Kleitman

    Daniel J. Kleitman. On a combinatorial conjecture of erdös. Journal of Combinatorial Theory, 1(2):209–214, 1966

    work page 1966

  14. [14]

    Greedoids.Springer, Jan 1991

    Bernhard Körte, Rainer Schräder, and László Lovász. Greedoids.Springer, Jan 1991

    work page 1991

  15. [15]

    John M. Lee. Introduction to topological manifolds.Springer, Jan 2011

    work page 2011

  16. [16]

    On the hardness of approximate reasoning.Artif

    Dan Roth. On the hardness of approximate reasoning.Artif. Intell., 82(1-2):273–302, 1996

    work page 1996

  17. [17]

    Combining component caching and clause learning for effective model counting

    TianSang, FahiemBacchus, PaulBeame, HenryA.Kautz, andToniannPitassi. Combining component caching and clause learning for effective model counting. InSAT 2004 - The Seventh International Conference on Theory and Applications of Satisfiability Testing, 10- 13 May 2004, Vancouver, BC, Canada, Online Proceedings, 2004

    work page 2004

  18. [18]

    Stanley.Enumerative Combinatorics, volume 1

    Richard P. Stanley.Enumerative Combinatorics, volume 1. Cambridge University Press, USA, 2nd edition, 2011. pg. 282

    work page 2011

  19. [19]

    Springer Nature, 2022

    Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch.Probabilistic databases. Springer Nature, 2022

    work page 2022

  20. [20]

    Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410–421, 1979

    work page 1979

  21. [21]

    Basing decisions on sentences in decision diagrams

    Yexiang Xue, Arthur Choi, and Adnan Darwiche. Basing decisions on sentences in decision diagrams. In Jörg Hoffmann and Bart Selman, editors,Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, pages 842–849. AAAI Press, 2012. 14 A Deferred proofs A.1 Proof of theorem 4.8 We claim that for ...

    work page 2012