CNF Encodings of Symmetric Functions
Authors:
Preprint
- 26 July 2023
- preprint
- Published by Springer Nature in Research Square
Abstract
Many Boolean functions that need to~be encoded as~CNF in~practice, have only exponential size CNF representations. To~avoid this effect, one usually introduces nondeterministic variables. For example, whereas the minimum number of~clauses in a~CNF computing the parity function $x_1\oplus x_2 \oplus \dotsb \oplus x_n$ is~$2^{n-1}$, one can use $n-1$ nondeterministic variables to~get a~CNF encoding with $4n$~clauses. In~this paper, we prove tradeoffs between various parameters (the number of~clauses, the width of~clauses, and the number of~nondeterministic variables) of~CNF encodings of~various symmetric functions. In~particular, we~show that a~folklore way of~encoding parity as~CNF is~provably optimal. We~do this by~using a~tight connection between CNF encodings and depth-3 circuits. This connection shows that CNF encodings is an~interesting computational model for Boolean functions: on~the one hand, it~is routinely used in~practice when translating a~practical computational problem to~a~format acceptable by a~SAT solver, on~the other hand, lower bounds on~the size of~CNF encodings imply depth-3 circuit lower bounds.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- SAT Encodings of the At-Most-k Constraint2019
- A lower bound on CNF encodings of the at-most-one constraintTheoretical Computer Science, 2019
- Boolean Function Complexity2012
- New upper bounds on the Boolean circuit complexity of symmetric functionsInformation Processing Letters, 2010
- Towards an Optimal CNF Encoding of Boolean Cardinality Constraints2005
- SAT problems with chains of dependent variablesDiscrete Applied Mathematics, 2003
- Top-down lower bounds for depth 3 circuits2002
- Proving Consistency Assertions for Automotive Product Data ManagementJournal of Automated Reasoning, 2000
- Radio Link Frequency AssignmentConstraints, 1999
- Graph-theoretic arguments in low-level complexity1977