The CNF Encoding Complexity of Boolean FunctionsResearch Paper
A CNF encoding of a boolean function is a CNF formula over the input variables and extra auxiliary variables such that exactly when some setting of the auxiliaries satisfies the formula. Encodings of this kind are how problems are handed to SAT solvers, and the choice of encoding is often decisive for whether a problem can be…