Proof Systems Based on Structured Circuits
Christoph Berkholz, Matthäus Micun · 2026
Read Proof Systems Based on Structured Circuits by Christoph Berkholz, Matthäus Micun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12378.txt.
Introduction
Micun and Berkholz extend a family of proof systems that write each proof line as a compact diagram for a Boolean function. Earlier systems used ordered binary decision diagrams, studied since 2004. The authors switch to sentential decision diagrams and deterministic structured DNNF circuits, which can be even more compact. Both new variants give strictly smaller refutations of unsatisfiable formulas than the older diagrams. They also map how the systems' power shifts with the derivation rules allowed.
Catalog record
| CREATOR | Christoph Berkholz, Matthäus Micun |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76573 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12378
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Proof Systems Based on Structured Circuits Christoph Berkholz, Matthäus Micun Abstract Since their introduction by Atserias, Kolaitis, and Vardi in 2004, proof systems where each line is represented by an ordered binary decision diagram (OBDD) have been intensively studied as they allow to compactly represent Boolean functions. We extend this line of work by considering representation formats that can be even more succinct than OBDDs and have gained a lot of attention in the area of knowledge compilation: sentential decision diagrams (SDDs) and deterministic structured DNNF circuits (d-SDNNFs). We show that both variants can provide strictly smaller refutations of unsatisfiable CNFs than their OBDD counterparts. Furthermore, we investigate the relative strength of these systems depending on which of the three fundamental derivation rules join, reordering, and weakening are allowed. Here we obtain several separations and identify interesting open problems. To streamline our proofs we establish a sat-to-unsat lifting theorem that might be of independent interest: it turns satisfiable CNFs that are hard to represent by SDDs and d-SDNNFs into unsatisfiable CNFs that are hard to refute in the corresponding proof system. Technische Universität Ilmenau, [email protected] by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 414325841.Technische Universität Ilmenau, [email protected] by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 414325841. keywords Proof Complexity, Sentential Decision Diagram, DNNF, OBDD ccs Theory of computation Proof complexity † † runningauthor: C. Berkholz and M. Micun † † copyright: Christoph Berkholz, Matthäus Micun {CCSXML} <ccs2012> <concept> <concept_id>10003752.10003777.10003785</concept_id> <concept_desc>Theory of computation Proof complexity</concept_desc> <concept_significance>500</concept_significance> </concept> </ccs2012> 1 Introduction Propositional proof systems where every line is represented by an Ordered Binary Decision Diagram (OBDD) have been introduced in 2004 [ 2 ] and have been intensively studied since then [ 7 , 19 , 11 , 10 , 12 , 6 , 13 ] (see [ 6 ] for an overview). One main feature of the approach to take OBDDs instead of simpler objects such as disjunctive clauses is that even complex Boolean functions can be succinctly represented as OBDDs, which then results in more succinct proofs. At the same time, important operations such as equivalence, entailment, and satisfiability tests can be implemented in polynomial time on OBDDs, which is a prerequisite for designing useful and efficiently verifiable derivation rules. OBDDs also play a fundamental role in knowledge compilation , an area pioneered in [ 8 ] that studies different representation formats for Boolean functions with a particular focus on the trade-off between succinctness and usefulness . Motivated by recent advances in that field, the central question we want to answer with this paper is whether there are more succinct representation formats that are still useful enough to serve as a basis for a proof system and whether these systems lead to strictly smaller refutations of unsatisfiable CNFs than OBDD-based systems. We identify two such representation formats. The first one are Sentential Decision Diagrams (SDDs) introduced in [ 9 ] . SDDs generalise OBDDs by branching not only on a single variable, but on several variables at the same time. Moreover, while each OBDD respects some linear order on the variables, structure is enforced in SDDs by a variable tree (vtree). Similarly to OBDDs, they also have several nice algorithmic properties, such as polynomial time conjunction and negation. On the other hand, SDDs can be strictly more succinct than OBDDs [ 18 , 5 ] . The second representation format we consider are deterministic structured circuits in Decomposable Negation Normal Form (d-SDNNF), which have been introduced in [ 16 ] . Here, variables are also structured along a vtree and d-SDNNFs generalise SDDs. In fact, it has recently be shown that d-SDNNFs can be strictly more succinct that SDDs [ 21 ] . While being more succinct, they also lose some important algorithmic properties; luckily not the ones we need to use as a basis for a proof system. OBDD( \land,r,w ) OBDD( \land,w ) Resolution OBDD( \land,r ) OBDD( \land ) d-SDNNF( \land,r^{\ast},w ) d-SDNNF( \land,w ) d-SDNNF( \land,r^{\ast} ) d-SDNNF( \land ) Figure 1: The various OBDD- and d-SDNNF-based proof systems. A solid edge from A to B implies that proof system A polynomially simulates proof system B , that is, A is at least as succinct as B . A dotted edge from A to B indicates that no superpolynomial separation between A and B is known. If there is no path from A to B using solid or dotted edges, then A does not polynomially simulate B . Dotted edges from OBDD (\land,w) to d-SDNNF (\land) as well as from OBDD (\land,r,w) to every d-SDNNF proof system are implied, but left out for legibility. The main contribution of this paper is to introduce proof systems based on these representation formats and to analyse the relative succinctness compared to their OBDD counterparts and to each other. The derivation rules of the new systems mimic the ones that have been studied for OBDD-based systems: if we have derived D^{\prime},D^{\prime\prime} , the join ( \land ) rule allows us to infer the conjunction D=D^{\prime}\land D^{\prime\prime} provided that D^{\prime} and D^{\prime\prime} respect the same order/vtree; the reordering (r) rule allows us to infer D from an equivalent D^{\prime} with a different order/vtree; the weakening (w) rule allows us to infer D from D^{\prime} over the same order/vtree if D^{\prime} entails D . Since in some cases reordering of vtrees is not known to be polynomial time verifiable, we introduce a small restructuring rule (r^{\ast}) that is verifiable and modifies the vtree only locally. However, even with this restricted rule, the SDD/d-SDNNF-systems still polynomially simulate their OBDD counterparts with one-step reordering (r) . Figure 1 depicts the obtained simulations and separations between OBDD and d-SDNNF-based proof systems. The proof systems based on SDDs are not included for simplicity, as all separations and simulations agree with the d-SDNNF case. In fact, we leave it as open problem, whether d-SDNNF circuits (that can be more succinct than SDDs) prove a strictly more powerful propositional proof system. Technical contributions Our first technical contribution is a method for lifting lower bounds on the size of OBDDs/SDDs/d-SDNNFs that represent the models of a satisfiable CNF \varphi to a lower bound on the proof size for refuting an unsatisfiable CNF \mathcal{Z}(\varphi) in a corresponding proof system without weakening (Theorem 13 ). This method can be applied to a broad class of (k,\log n) -CNFs, where every clause has at most k literals and every variable appears in at most \log n clauses. We then use this method to obtain several separations in Section 5 . In particular, we show that in the absence of weakening, SDD and d-SDNNF proof systems cannot be polynomially simulated by their OBDD-counterparts and are indeed strictly stronger (Section 5.1 ). We also apply the lifting method to obtain separations between different variants of these proof systems. These separations have been known for OBDD proof system (see [ 6 ] for an overview) and the challenge is to show that the lower bound constructions are also hard for the stronger SDD/d-SDNNF format. Besides applying the lifting method (Theorem 13 ), we also use the connection between structured circuits and rectangle covers in communication complexity (see [ 4