betaFeedback

WorksComputer Science

The CNF Encoding Complexity of Boolean Functions

Abstract

We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time tt (in the RAM model) with mm bits of advice such that at most bb bits of advice are accessed for each input, then it admits a CNF encoding with O~(t+mb)\widetilde{O}(t + \sqrt{mb}) clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook–Levin theorem, for which a naïve generalization would yield O~(t+m)\widetilde{O}(t+m) clauses; our applications leverage b=o(m)b = o(m) to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every kk-CNF function on nn inputs can be encoded with nk/2Ωk(lg⁡n)n^k/2^{Ω_k(\sqrt{\lg n})} clauses. Notably, despite encoding a kk-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is Ωk(nk/lg⁡n)Ω_k(n^{k}/\lg n) in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.

Introduction

Given a boolean function ff, how compactly can we “encode” ff as a CNF formula (see Definition 1)? A partial answer was provided first by the Cook–Levin theorem [12, 42], which implies that if ff can be computed nondeterministically in nn steps, then it can be encoded as a CNF instance of size nO(1)n^{O(1)}. Since then, more compact encodings of size O~(n)\widetilde{O}(n) have been devised and extended to different models of computation [56, 51, 13, 55]. These optimized Cook–Levin theorems have several complexity-theoretic applications, including showing that CNF-SAT is complete for nondeterministic quasilinear time [56, 23] and proving time-space tradeoffs for CNF-SAT [21]. The problem of compactly encoding boolean functions has also acquired tremendous practical utility with the advent of SAT solvers, where efficient encodings are often make-or-break for whether a problem can be solved in practice [58, 37 HS24, 54, 28]; empirically, smaller encodings tend to perform better in practice [Bjӧ09, ANORC13].1

Consequently, the SAT community has studied encodings for a variety of concrete functions, including both classical NP-complete problems (e.g., Hamiltonian cycle [69, 70], graph coloring [17], kk-clique [31, 60], and many others [10]) as well as elementary constraints such as parity [16] or at-most-kk [59, 41, 36], which serve as building blocks of larger encodings. However, despite the theoretical and practical importance of CNF encodings, this model of computation has yet to receive a systematic theoretical treatment that focuses on large classes of boolean functions rather than particular instances, which is in stark contrast to other models of computation like boolean circuits [32]. In this paper, we prove fundamental results about the complexity of boolean functions in this model and show how this complexity metric relates to complexities in other nonuniform models. We hope to convince the reader that the theory of CNF encodings is much deeper than has previously been appreciated. In particular, we show that the optimized Cook–Levin results mentioned above are not the end of the story.

A CNF encoding of a boolean function ff is a CNF formula with nondeterministic variables that computes ff. Formally:

Definition 1 (Encoding). Given a boolean function f:{0,1}n→{0,1}f : \{0,1\}^{n} \to\{0,1\}, we say that a triple (φ,X,Y)(\varphi, X, Y) is an encoding of ff if: (i) X:=(x1,…,xn)X := (x_1, \ldots, x_n) is a sequence of propositional variables, and YY is a set of propositional variables disjoint from XX; (ii) φ\varphi is a CNF formula over variables X⊔YX \sqcup Y; and (iii) for every assignment τ:X→{0,1}\tau: X \to\{0,1\},

f(τ(x1),…,τ(xn))=1⟺∃θ:Y→{0,1},  (τ∪θ)⊨φ.f\bigl(\tau(x_1),\ldots,\tau(x_n)\bigr)=1 \Longleftrightarrow\exists\theta:Y\to\{0,1\},\;(\tau\cup\theta)\models\varphi.

The variables in XX are called input variables, and those in YY are called auxiliary variables.

:::

Thus, CNF encodings constitute a nondeterministic, nonuniform model of computation. We say that the CNF encoding complexity of a boolean function ff, denoted enc⁡(f)\operatorname{enc}(f), is the minimum number of clauses in a CNF encoding of ff. In Section 1.3, we elaborate on why we choose to focus on the clause count instead of, say, the total number of literals in a CNF encoding.

One of the few theoretical results known about encoding complexity is due to Tseitin [65]: if the (nondeterministic) circuit complexity of ff is nn, then enc⁡(f)=O(n)\operatorname{enc}(f)=O(n). Each of our main results implies that the converse of Tseitin’s theorem fails strongly: there are boolean functions for which $\operatorname{enc}(f) is much smaller than its (nondeterministic) circuit complexity. In § 6, we characterize enc⁡(f)\operatorname{enc}(f) exactly in terms of nondeterministic conjunctive circuit complexity: whenever enc⁡(f)≥2\operatorname{enc}(f) \ge2, it equals the minimum number of wires entering ∧\land-gates in a nondeterministic De Morgan circuit computing ff. Thus, all of our results also have circuit complexity analogues.

Our results

Our first result relates encoding complexity to the time complexity of nondeterministic RAM machines with advice. Robson [55] showed the following variant of the Cook–Levin theorem: if f:{0,1}n→{0,1}f:\{0,1\}^{n} \to\{0,1\} can be computed by a nondeterministic RAM machine in time t≥nt \ge n, then enc⁡(f)=O(tlg⁡t)\operatorname{enc}(f)=O(t\lg t), and such an encoding can be constructed in polynomial time (strictly speaking, if the machine has program size pp, Robson yields O((t+p)lg⁡(t+p))O((t+p)\lg(t+p))). However, there is a precise sense in which Robson’s result does not capture the full power of CNF encodings; nondeterministic RAM is a uniform model of computation, whereas CNF encodings constitute a nonuniform model. Thus, it is natural to instead translate nondeterministic RAM machines with advice (a model we call ANRAM) to CNF encodings. A naïve extension of Robson’s result would state that if ff can be computed by an ANRAM machine in time tt with mm bits of advice, then enc⁡(f)=O~(t+m)\operatorname{enc}(f)=\widetilde{O}(t+m).2 We show the following quantitative improvement:

Theorem 2. Let f:{0,1}n→{0,1}f:\{0,1\}^{n} \to\{0,1\}, and suppose that ff can be evaluated in time t≥nt \ge n with mm bits of advice by an ANRAM machine that accesses at most bb bits of the advice for each input. Then, enc⁡(f)=O~(t+mb)\operatorname{enc}(f)=\widetilde{O}(t+\sqrt{mb}). Furthermore, such an encoding can be constructed deterministically in time polynomial in n+t+mn+t+m given the advice string.

We find Theorem 2 remarkable. It provides a tight bound on the number of clauses (up to polylogarithmic factors) for a wide variety of functions (technically speaking, even for a 1−o(1)1-o(1) fraction of all boolean functions), and yields encodings with fewer clauses for a variety of classical NP-complete problems (we discuss some in Section 1.2). In contrast, applying Robson’s result yields quadratically worse bounds for almost all functions. Indeed, suppose one takes f:{0,1}n→{0,1}f:\{0,1\}^{n} \to\{0,1\} to be an arbitrary boolean function. Then, letting the advice string AA be the string of length 2n2^{n} encoding ff’s truth table, we can compute ff by reading the input x⃗\vec{x} and consulting A[x⃗]=f(x⃗)A[\vec{x}]=f(\vec{x}); this way t=O(n)t=O(n), m=2nm=2^{n}, and b=1b=1, which yields enc⁡(f)=O~(2n)\operatorname{enc}(f)=\widetilde{O}(\sqrt{2^{n}}). In contrast, an application of Robson’s theorem would yield the trivial bound enc⁡(f)=O~(2n)\operatorname{enc}(f)=\widetilde{O}(2^{n}).3

In fact, a simple lower bound shows that Theorem 2 is not too far from optimal, meaning roughly that for every boolean function ff, there is some ANRAM machine for which applying Theorem 2 yields an encoding of size at most enc⁡(f)3/2\operatorname{enc}(f)^{3/2}.

Proposition 3. Let f:{0,1}n→{0,1}f:\{0,1\}^{n} \to\{0,1\} be a boolean function with enc⁡(f)=Ω(n)\operatorname{enc}(f)=\Omega(n), let (Mf⋆,Af⋆)(M_f^\star,A_f^\star) be an ANRAM machine that computes ff and minimizes t+mbt+\sqrt{mb} over all possible (machine, advice) pairs, and let t⋆,m⋆,b⋆t^\star,m^\star,b^\star be the corresponding optimal parameters. Then,

enc⁡(f)=Ω~((t⋆+m⋆b⋆)2/3).\operatorname{enc}(f)=\widetilde{\Omega}\left(\left(t^\star+\sqrt{m^\star b^\star}\right)^{2/3}\right).

Proof. Let FF be a formula that encodes ff with enc⁡(f)\operatorname{enc}(f) clauses, and YY be its set of auxiliary variables. We can further assume that ∣Y∣≤enc⁡(f)\lvert Y\rvert\le\operatorname{enc}(f); we prove that this assumption is without loss of generality in Proposition 30. Then, consider the ANRAM machine receiving FF as advice, and upon receiving an input x⃗\vec{x}, proceed as follows. First, guess an assignment θ\theta for each of the auxiliary variables in time O(∣Y∣)=O(enc⁡(f))O(\lvert Y\rvert)=O(\operatorname{enc}(f)). Next, for each clause in FF, nondeterministically guess which of its at most n+enc⁡(f)n+\operatorname{enc}(f) literals satisfies it; guessing this index takes time O(lg⁡(enc⁡(f)))O(\lg(\operatorname{enc}(f))). Then, check that the polarity of that literal matches its value on the input, or on θ\theta if it corresponds to an auxiliary variable, which can be done in time O(lg⁡(enc⁡(f)))O(\lg(\operatorname{enc}(f))), and accept if and only if all such checks succeed. Thus, the total time is t=O(enc⁡(f)lg⁡(enc⁡(f)))t=O(\operatorname{enc}(f)\lg(\operatorname{enc}(f))), the advice length is m=O~(enc⁡(f)2)m=\widetilde{O}(\operatorname{enc}(f)^2) and the number of bits read is b=O~(enc⁡(f))b=\widetilde{O}(\operatorname{enc}(f)). We thus have

t+mb=O~(enc⁡(f))+O~(enc⁡(f)2)⋅O~(enc⁡(f))=O~(enc⁡(f)3/2).t+\sqrt{mb}=\widetilde{O}(\operatorname{enc}(f))+\sqrt{\widetilde{O}(\operatorname{enc}(f)^2)\cdot\widetilde{O}(\operatorname{enc}(f))}=\widetilde{O}(\operatorname{enc}(f)^{3/2}).

Since t+mb≥t⋆+m⋆b⋆t+\sqrt{mb}\ge t^\star+\sqrt{m^\star b^\star} by definition, we obtain O~(enc⁡(f)3/2)≥t⋆+m⋆b⋆\widetilde{O}(\operatorname{enc}(f)^{3/2})\ge t^\star+\sqrt{m^\star b^\star} from which the result follows.

More generally, Theorem 2 has a natural interpretation in terms of data structures. Suppose we have an algorithm to compute ff that has access to a data structure DfD_f which uses mm bits of memory, and upon receiving an input x⃗\vec{x}, nondeterministically computes f(x⃗)f(\vec{x}) in time tt by querying at most bb bits of DfD_f. Then, Theorem 2 says that ff must have a small CNF encoding, regardless of how long it takes to build DfD_f. As a more interesting application, consider the functions ISG:{0,1}n→{0,1}\mathrm{IS}_G:\{0,1\}^n\to\{0,1\}, each parametrized by some graph GG on nn vertices v1,…,vnv_1,\ldots,v_n, defined by

ISG(x1,…,xn)=1⟺{vi∣xi=1} is an independent set of G.\mathrm{IS}_G(x_1,\ldots,x_n)=1\Longleftrightarrow\{v_i\mid x_i=1\}\text{ is an independent set of }G.

References

  1. [1][AFWZ95] Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman. Derandomized graph products. Comput. Complex., 5(1):60–75, 1995. doi:10.1007/BF01277956. 9, 23DOI
  2. [2][AL86] Ron Aharoni and Nathan Linial. Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. Journal of Combinatorial Theory, Series A, 43(2):196–204, 1986. URL: https://www.sciencedirect.com/science/article/pii/0097316586900609, doi:10.1016/0097-3165(86)90060-9. 29DOI
  3. [4][AWY15] Amir Abboud, R. Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 218–230. SIAM, 2015. doi:10.1137/1.9781611973730.17. 15, 16DOI
  4. [5][BDL+23] József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, and Yufei Zhao. Nearly all k-SAT functions are unate. In STOC’23—Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 958–962. ACM, New York, 2023. doi:10.1145/3564246.3585123. 3, 5DOI
  5. [6][Bjö09] Magnus Björk. Successful SAT encoding techniques. Journal on Satisfiability, Boolean Modeling and Computation, 7(4):189–201, 2009. doi:10.3233/SAT190085. 1, 6DOI
  6. [7]Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM Journal on Computing, 28(5):1627–1640, 1999. doi:10.1137/S0097539795294165. 9, 31DOI
  7. [8]Guy E. Blelloch, Virginia Vassilevska, and R. Ryan Williams. A new combinatorial approach for sparse graph problems. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 108–120. Springer, 2008. doi:10.1007/978-3-540-70575-8_10. 6DOI
  8. [9]Nikhil Bansal and R. Ryan Williams. Regularity lemmas and combinatorial algorithms. Theory Comput., 8(1):69–94, 2012. URL: https://doi.org/10.4086/toc.2012.v008a004, doi:10.4086/TOC.2012.V008A004. 6
  9. [10]Bruno Courcelle and Irène Durand. On using SAT solvers for graph computations. Discret. Appl. Math., 380:348–366, 2026. URL: https://doi.org/10.1016/j.dam.2025.10.017, doi:10.1016/J.DAM.2025.10.017. 1
  10. [11]László Csirmaz, Péter Ligeti, and Gábor Tardos. Erdős-Pyber theorem for hypergraphs and secret sharing. Graphs Combin., 31(5):1335–1346, 2015. doi:10.1007/s00373-014-1448-7. 3, 28DOI
  11. [12]Stephen A. Cook. The complexity of theorem-proving procedures. In Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman, editors, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151–158. ACM, 1971. doi:10.1145/800157.805047. 1DOI
  12. [13]Stephen A. Cook. Short propositional formulas represent nondeterministic computations. Information Processing Letters, 26(5):269–270, 1988. 1DOI
  13. [14]Timothy M. Chan and R. Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov–Smolensky. ACM Trans. Algorithms, 17(1), December 2020. doi:10.1145/3402926. 9, 15, 16, 17DOI
  14. [16]Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, and Nikita Slezkin. CNF encodings of symmetric functions. Theory Comput. Syst., 68(5):1291–1311, 2024. URL: https://doi.org/10.1007/s00224-024-10168-w, doi:10.1007/S00224-024-10168-W. 1
  15. [17]Daniel Faber, Adalat Jabrayilov, and Petra Mutzel. SAT encoding of partial ordering models for graph coloring problems. In Supratik Chakraborty and Jie-Hong Roland Jiang, editors, 27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024, Pune, India, August 21-24, 2024, volume 305 of LIPICs, pages 12:1–12:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.SAT.2024.12, doi:10.4230/LIPICS.SAT.2024.12. 1
  16. [19]Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. J. Comput. System Sci., 51(2):261–272, 1995. doi:10.1006/jcss.1995.1065.DOI
  17. [21]Lance Fortnow. Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci., 60(2):337–353, 2000. URL: https://doi.org/10.1006/jcss.1999.1671, doi:10.1006/jcss.1999.1671.
  18. [22]M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  19. [23]Yuri Gurevich and Saharon Shelah. Nearly linear time. In Albert R. Meyer and Michael A. Taitslin, editors, Logic at Botik ’89, Symposium on Logical Foundations of Computer Science, Pereslav-Zalessky, USSR, July 3-8, 1989, Proceedings, Lecture Notes in Computer Science, pages 108–118. Springer, 1989. doi:10.1007/3-540-51237-3_10.DOI
  20. [24]Vijay Ganesh and Moshe Y. Vardi. On the unreasonable effectiveness of SAT solvers. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 547–566. Cambridge University Press, 2021. URL: https://www.cambridge.org/core/product/58F65AA9F1D3B027CB02D05099C7929B, doi:10.1017/9781108637435.032.DOI
  21. [25]Philip Hall. On representatives of subsets. J. London Math. Soc., 10(1):26–30, 1935. doi:10.1112/jlms/s1-10.37.26.DOI
  22. [26]Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006. URL: https://www.math.ias.edu/~avi/BOOKS/expanderbookr1.pdf, doi:10.1090/S0273-0979-06-01126-8.DOI
  23. [27]Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, and Renfei Zhou. Optimal static dictionary with worst-case constant query time. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 278–289, 2025. doi:10.1145/3717823.3718278.
  24. [28]Marijn J. H. Heule and Stefan Szeider. A SAT approach to clique-width. ACM Trans. Comput. Logic, 16(3), June 2015. doi:10.1145/2736696.DOI
  25. [30]Pavel Hrubeš and Navid Talebanfard. On the extension complexity of polytopes separating subsets of the Boolean cube. Discrete Comput. Geom., 70(1):268–278, 2023. doi:10.1007/s00454-022-00419-3. 7DOI
  26. [31]Alexey Ignatiev, António Morgado, and João Marques-Silva. Cardinality encodings for graph optimization problems. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 652–658. ijcai.org, 2017. URL: https://doi.org/10.24963/ijcai.2017/91, doi:10.24963/IJCAI.2017/91. 1
  27. [32]Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. doi:10.1007/978-3-642-24508-4. 1, 7
  28. [33]Stasys Jukna. Computational complexity of graphs. In Matthias Dehmer, Abbe Mowshowitz, and Frank Emmert-Streib, editors, Advances in Network Complexity, chapter 5, pages 99–153. Wiley, 2013. URL: https://onlinelibrary.wiley.com/doi/10.1002/9783527670468.ch05, doi:10.1002/9783527670468.ch05. 7DOI
  29. [34]Benjamin Kiesl, Marijn J. H. Heule, and Armin Biere. Truth assignments as conditional autarkies. In Yu-Fang Chen, Chih-Hong Cheng, and Javier Esparza, editors, Automated Technology for Verification and Analysis, pages 48–64. Springer International Publishing, 2019. 29DOI
  30. [35]Donald E. Knuth. The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2. Addison-Wesley Professional, 2022. Section 7.2.2.2: Satisfiability. 6
  31. [36]Andrew Krapivin, Benjamin Przybocki, and Bernardo Subercaseaux. Near-optimal encodings of cardinality constraints. In Alexey Ignatiev and Stefan Szeider, editors, 29th International Conference on Theory and Applications of Satisfiability Testing, SAT 2026, Lisbon, Portugal, July 20-23, 2026, volume 377 of LIPIcs, pages 23:1–23:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. URL: https://doi.org/10.4230/LIPIcs.SAT.2026.23, doi:10.4230/LIPIcs.SAT.2026.23. 1, 6, 12
  32. [37]Markus Kirchweger, Tomáš Peitl, Bernardo Subercaseaux, and Stefan Szeider. From the finite to the infinite: Sharper asymptotic bounds on Norin’s conjecture via SAT, 2025. URL: https://arxiv.org/abs/2511.08386, arXiv:2511.08386. 1
  33. [38]Andrew Krapivin, Benjamin Przybocki, Nicolás Sanhueza-Matamala, and Bernardo Subercaseaux. Optimal and efficient partite decompositions of hypergraphs. In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, pages 2187–2198. ACM, 2026. doi:10.1145/3798129.3800921. 3, 28DOI
  34. [39]William Kretschmer. Quantum mass production theorems. In Omar Fawzi and Michael Walter, editors, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023, Aveiro, Portugal, July 24-28, 2023, volume 266 of LIPIcs, pages 10:1–10:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.TQC.2023.10, doi:10.4230/LIPIcs.TQC.2023.10. 7, 11
  35. [41]Petr Kučera, Petr Savický, and Vojtěch Vorel. A lower bound on CNF encodings of the at-most-one constraint. Theor. Comput. Sci., 762:51–73, 2019. doi:10.1016/J.TCS.2018.09.003. 1
  36. [42]Leonid A. Levin. Universal’nye zadachi perebora. Problemy Peredachi Informatsii, 9(3):115–116, 1973. English translation: Universal sequential search problems, Problems of Information Transmission 9(3):265–266, 1973. 1
  37. [43]Oleg B. Lupanov. On a method of circuit synthesis. Izvestiya Vysshikh Uchebnykh Zavedeniy, Radiofizika, 1:120–140, 1958. (in Russian). 4
  38. [44]Kasper Green Larsen and R. Ryan Williams. Faster online matrix-vector multiplication. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2182–2189. SIAM, 2017. doi:10.1137/1.9781611974782.142. 3, 6, 9, 15, 16DOI
  39. [46]Burkhard Monien and Ewald Speckenmeyer. Solving satisfiability in less than 2ⁿ steps. Discrete Applied Mathematics, 10(3):287–295, 1985. URL: https://www.sciencedirect.com/science/article/pii/0166218X85900502, doi:10.1016/0166-218X(85)90050-2. 9, 29DOI
  40. [47]Éduard Ivanovich Nechiporuk. On the complexity of schemes in some bases containing nontrivial elements with zero weights. Problemy Kibernetiki, 8:123–160, 1962. (in Russian). 4, 7, 9, 31
  41. [48]Éduard Ivanovich Nechiporuk. The topological principles of self-correction. Problemy Kibernet., (21):5–102, 1969. Available in Russian at https://web.vu.lt/mif/s.jukna/boolean/Russians/Nechiporuk-1969a.pdf, thanks to Stasys Jukna. 19
  42. [49]Rasmus Pagh. Low redundancy in static dictionaries with constant query time. SIAM Journal on Computing, 31(2):353–363, 2001. URL: https://www.rasmuspagh.net/papers/dict-jour.pdf, doi:10.1137/S0097539700369909. 9, 31DOI
  43. [51]Nicholas Pippenger and Michael J Fischer. Relations among complexity measures. Journal of the ACM (JACM), 26(2):361–381, 1979. 1DOI
  44. [52]Steven D. Prestwich. CNF encodings. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability - Second Edition, volume 336 of Frontiers in Artificial Intelligence and Applications, pages 75–100. IOS Press, 2021. doi:10.3233/FAIA200985. 1
  45. [53]Benjamin Przybocki, Bernardo Subercaseaux, and Marijn J. H. Heule. Automated reencoding meets graph theory. In Alexey Ignatiev and Stefan Szeider, editors, 29th International Conference on Theory and Applications of Satisfiability Testing, SAT 2026, Lisbon, Portugal, July 20-23, 2026, volume 377 of LIPIcs, pages 29:1–29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. URL: https://doi.org/10.4230/LIPIcs.SAT.2026.29, doi:10.4230/LIPIcs.SAT.2026.29. 3, 7
  46. [54]Long Qian, Eric Wang, Bernardo Subercaseaux, and Marijn J. H. Heule. Unfolding boxes with local constraints. In Automated Deduction – CADE 30: 30th International Conference on Automated Deduction, Stuttgart, Germany, July 28-31, 2025, Proceedings, pages 736–754, Berlin, Heidelberg, 2025. Springer-Verlag. doi:10.1007/978-3-031-99984-0_38. 1DOI
  47. [55]John M Robson. An O(T log T) reduction from RAM computations to satisfiability. Theoretical Computer Science, 82(1):141–149, 1991. 1, 2, 7, 9, 10DOI
  48. [56]Claus-Peter Schnorr. Satisfiability is quasilinear complete in NQL. Journal of the ACM (JACM), 25(1):136–145, 1978. 1DOI
  49. [58]Bernardo Subercaseaux and Marijn J. H. Heule. The packing chromatic number of the infinite square grid is 15. In Sriram Sankaranarayanan and Natasha Sharygina, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 389–406. Springer Nature Switzerland, 2023. 1, 6DOI
  50. [59]Carsten Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In Peter van Beek, editor, Principles and Practice of Constraint Programming - CP, volume 3709 of Lecture Notes in Computer Science, pages 827–831. Springer, 2005. doi:10.1007/11564751_73. 1DOI
  51. [60]Bernardo Subercaseaux. Asymptotically smaller encodings for graph problems and scheduling, 2025. (ModRef workshop). URL: https://arxiv.org/abs/2506.14042, arXiv:2506.14042. 1, 3, 5, 7
  52. [61]Zimo Sheng and Mingyu Xiao. A near-linear element kernel for d-hitting set, 2026. URL: https://arxiv.org/abs/2609.06512, arXiv:2609.06512. 7
  53. [62]Zimo Sheng and Mingyu Xiao. A polynomial kernel for planar directed feedback vertex set, 2026. URL: https://arxiv.org/abs/2609.23669, arXiv:2609.23669. 7
  54. [63]Endre Szemerédi. Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978. 25
  55. [64]Jason Teutsch. Short lists for shortest descriptions in short time. Computational Complexity, 23(4):565–583, 2014. URL: https://arxiv.org/abs/1212.6104. 8, 13
  56. [65]Grigori S. Tseytin. On the complexity of derivation in propositional calculus. In A. O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, Part II, pages 115–125. Consultants Bureau, 1970. Translated from Russian (1968). 1
  57. [66]Dietmar Ulig. On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Mathematical Notes of the Academy of Sciences of the USSR, 15(6):558–562, June 1974. doi:10.1007/bf01152835. 7, 11DOI
  58. [67]R. Ryan Williams. Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 995–1001. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283490. 6DOI
  59. [68]Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441–466, 1991. doi:10.1016/0022-0000(91)90024-Y. 6DOI
  60. [69]Neng-Fa Zhou. In pursuit of an efficient SAT encoding for the Hamiltonian cycle problem. In Helmut Simonis, editor, Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, volume 12333 of Lecture Notes in Computer Science, pages 585–602. Springer, 2020. doi:10.1007/978–3–030–58475–7_34. 1, 4DOI
  61. [70]Neng-Fa Zhou. Encoding the Hamiltonian cycle problem into SAT based on vertex elimination (short paper). In Paul Shaw, editor, 30th International Conference on Principles and Practice of Constraint Programming, CP 2024, Girona, Spain, September 2-6, 2024, volume 307 of LIPIcs, pages 40:1–40:8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.CP.2024.40. 1DOI

Paper details

vlnc:W_vukb9knq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents