Simplifier: A New Tool for Boolean Circuit Simplification
Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin · 2025
Read Simplifier: A New Tool for Boolean Circuit Simplification by Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin (2025) 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-2503-19103.txt.
Introduction
Daniil Averkov and co-authors introduced Simplifier in 2025, an open tool that shrinks Boolean circuits. A smaller circuit must still compute the same function as the first one. The problem links to logic design, checking, and solving tasks across computing.
The tool improves small parts of a circuit, each with three inputs and at most three outputs. It draws on a ready-made set of best small circuits, built with solvers after grouping like functions. Checking only a linear number of parts keeps one pass fast, often a few seconds. On standard test sets, it cut size further after a top existing tool, and by much more on another format.
Catalog record
| CREATOR | Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-19103
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Simplifier: A New Tool for Boolean Circuit Simplification Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin Abstract The Boolean circuit simplification problem involves finding a smaller circuit that computes the same function as a given Boolean circuit. This problem is closely related to several key areas with both theoretical and practical applications, such as logic synthesis, satisfiability, and verification. In this paper, we present Simplifier , a new open source tool for simplifying Boolean circuits. The tool optimizes subcircuits with three inputs and at most three outputs, seeking to improve each one. It is designed as a low-effort method that runs in just a few seconds for circuits of reasonable size. This efficiency is achieved by combining two key strategies. First, the tool utilizes a precomputed database of optimized circuits, generated with SAT solvers after carefully clustering Boolean functions with three inputs and up to three outputs. Second, we demonstrate that it is sufficient to check a linear number of subcircuits, relative to the size of the original circuit. This allows a single iteration of the tool to be executed in linear time. We evaluated the tool on a wide range of Boolean circuits, including both industrial and hand-crafted examples, in two popular formats: AIG and BENCH. For AIG circuits, after applying the state-of-the-art ABC framework, our tool achieved an additional 4% average reduction in size. For BENCH circuits, the tool reduced their size by an average of 30%. St. Petersburg State [email protected] École Polytechnique Fédérale de [email protected] Steklov Mathematical Institute at St. Petersburg, Russian Academy of [email protected]://orcid.org/0009-0003-0702-9973 JetBrains Research and https://alexanderskulikov.github.io [email protected]://orcid.org/0000-0002-5656-0336 Steklov Mathematical Institute at St. Petersburg, Russian Academy of [email protected]://orcid.org/0009-0004-2072-3457 JetBrains [email protected]://orcid.org/0000-0002-8241-5503 Neapolis University [email protected]://orcid.org/0009-0006-5187-8384 ccs Theory of computation Logic and verification ccs Theory of computation Complexity theory and logic ccs Theory of computation Circuit complexity keywords Boolean circuit, Boolean function, synthesis, verification, satisfiability, SAT, simplification, tool † † supplement: Source code repository: https://github.com/SPbSAT/simplifier † † runningauthor: D. Averkov, G. Emdin, V. Krivogornitsyna, A. Kulikov, F. Kurmazov, A. Smal, V. Vaskin † † copyright: Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Alexander Smal, Vsevolod Vaskin 1 Overview Boolean circuits as a way to represent Boolean functions appears in many applications, both in theory and in practice. In most cases, circuits are succinct and efficient descriptions of Boolean functions as the size of a circuit might be much smaller than the size of its truth-table (that is always 2^{n} for an n -variate Boolean function) or a CNF (that may also have exponential size). For example, the minimum number of clauses in a CNF formula that computes the parity function x_{1}\oplus\dotsb\oplus x_{n} is 2^{n-1} , whereas this function can be computed by a circuit of size n-1 over the full binary basis B_{2} and a circuit of size 3(n-1) over the basis \{\neg,\lor\} if one allows negations on the wires (see Figure 1 ). 0 00000 1 00001 1 00010 0 00011 1 00100 0 00101 0 00110 1 00111 1 01000 0 01001 0 01010 1 01011 0 01100 1 01101 1 01110 0 01111 1 10000 0 10001 0 10010 1 10011 0 10100 1 10101 1 10110 0 10111 0 11000 1 11001 1 11010 0 11011 1 11100 0 11101 0 11110 1 11111 truth-table: CNF formula: ({x_{1}}\lor{x_{2}}\lor{x_{3}}\lor{x_{4}}\lor{x_{5}})\land({x_{1}}\lor{x_{2}}\lor{x_{3}}\lor\overline{x_{4}}\lor\overline{x_{5}})\land({x_{1}}\lor{x_{2}}\lor\overline{x_{3}}\lor{x_{4}}\lor\overline{x_{5}})\land({x_{1}}\lor{x_{2}}\lor\overline{x_{3}}\lor\overline{x_{4}}\lor{x_{5}})\land({x_{1}}\lor\overline{x_{2}}\lor{x_{3}}\lor{x_{4}}\lor\overline{x_{5}})\land({x_{1}}\lor\overline{x_{2}}\lor{x_{3}}\lor\overline{x_{4}}\lor{x_{5}})\land({x_{1}}\lor\overline{x_{2}}\lor\overline{x_{3}}\lor{x_{4}}\lor{x_{5}})\land({x_{1}}\lor\overline{x_{2}}\lor\overline{x_{3}}\lor\overline{x_{4}}\lor\overline{x_{5}})\land(\overline{x_{1}}\lor{x_{2}}\lor{x_{3}}\lor{x_{4}}\lor\overline{x_{5}})\land(\overline{x_{1}}\lor{x_{2}}\lor{x_{3}}\lor\overline{x_{4}}\lor{x_{5}})\land(\overline{x_{1}}\lor{x_{2}}\lor\overline{x_{3}}\lor{x_{4}}\lor{x_{5}})\land(\overline{x_{1}}\lor{x_{2}}\lor\overline{x_{3}}\lor\overline{x_{4}}\lor\overline{x_{5}})\land(\overline{x_{1}}\lor\overline{x_{2}}\lor{x_{3}}\lor{x_{4}}\lor{x_{5}})\land(\overline{x_{1}}\lor\overline{x_{2}}\lor{x_{3}}\lor\overline{x_{4}}\lor\overline{x_{5}})\land(\overline{x_{1}}\lor\overline{x_{2}}\lor\overline{x_{3}}\lor{x_{4}}\lor\overline{x_{5}})\land(\overline{x_{1}}\lor\overline{x_{2}}\lor\overline{x_{3}}\lor\overline{x_{4}}\lor{x_{5}}) x_{1} x_{2} x_{3} x_{4} x_{5} \oplus \oplus \oplus \oplus circuit over B_{2} : x_{1} x_{2} x_{3} x_{4} x_{5} \land \land \land \land \land \land \land \land \land \land \land \land \land circuit over \{\land,\neg\} : Figure 1: Four representations of the function x_{1}\oplus x_{2}\oplus x_{3}\oplus x_{4}\oplus x_{5} : a truth table, a CNF, a circuit over the full binary basis B_{2} of size 4 , and a circuit over \{\neg,\land\} of size 12 (for the circuits, the dashed wires are negated, the output gate is shown in bold). Each of the shown representations is known to be optimal with respect to its size. 1.1 Circuit Synthesis In the circuit synthesis problem, one is given a specification of a Boolean function and needs to design a small circuit computing this function. The output of computer-aided design systems (that solve this problem) is often used in the manufacture of integrated circuits. The smaller the circuit, the easier and cheaper it is to produce: it has less functional elements, requires less wire crossings, etc. Whereas in practice various heuristic approaches are used, the circuit synthesis problem is also important from the theoretical point of view. There, it is known as the minimum circuit size problem (MCSP) : given a truth-table of a function, output a circuit of the minimum size computing this function. It is one of the central problems studied in meta-complexity theory [ 12 ] . MCSP is conjectured to not have a polynomial-time solution (note that we measure its complexity with respect to the truth-table size, i.e., it is not solvable in time 2^{O(n)} ). At the same time it is still an open question whether the general case of MCSP is NP-complete. Some researchers suggest that it might be NP-intermediate (neither in P nor NP-complete). The special cases of this problem for Boolean formulas in conjunctive normal form (CNF) or in disjunctive normal form (DNF) are well studied. These special cases of MCSP are known to be NP-hard [ 11 ] . Despite that, DNF-MCSP and CNF-MCSP are often solved in practice for small number of input variables using the widely known Quine–McCluskey algorithm [ 22 , 23 , 19 ] . There is also an alternative approach based on Binary Decision Diagrams (BDDs) [ 9 ] . However, Boolean functions that arise in practice, e.g., in VLSI design, have hundreds or even thousands of input variables and for it there is no hope of finding provably minimal circuits. 1.2 Circuit Simplification In this paper, we focus on the circuit simplification problem: given a Boolean circuit, find a circuit of smaller size computing the same function. It is a difficult problem as it generalizes the circuit satisfiability problem: checking whether a given circuit is unsatisfiable (that is, whether it computes the same as a trivial circuit that always outputs 0 ) is a special case of circuit simplification. In practice, before checking whether a given circuit is satisfiable or not, one usually first simplifies it. The simplification rules are also applied in the process of checking satisfiability (say, after assigning some inputs of the circuit). In applications like this one, it is crucial that a low-effort simplification method is used. Circuit simplification is also a close relative of circuit synthesis. On the one hand, one can use circuit simplification as a part of circuit synthesis as well as in postprocessing stages. On the other hand, one can even use circuit simplification directly for circuit synthesis: given a specification of a Boolean function, synthesize a naive circuit for it, then simplify it. Figure 2 shows two toy examples of circuit simplification. In the first example, the \oplus -gate has no outgoing edges (and it is not an output gate), thus it is redundant and can be removed from the circuit. In the second example, there are two gates that compute x_{2}\oplus x_{3} , and so