Circuits, cnfs, and satisfiability
Francis Zane, Ramamohan Paturi · 1998
This dissertation explores the connections between two seemingly unrelated problems: showing upper bounds on the running time of algorithms which solve the NP-complete satisfiability problem, and proving lower bounds on the complexity of Boolean circuits computing certain explicit hard functions. We show that both results follow from understanding the limitations of the expressive power of certain classes of Boolean formulae. We begin by analyzing RandomUC, a natural randomized algorithm for finding satisfying assignments of a k-CNF formula F, and show that, if F is satisfiable, RandomUC finds a satisfying assignment in time poly($n)2\sp{(1-1/k)n}$, significantly smaller than the poly($n)2\sp{n}$ required for exhaustive search. We then propose a new algorithm ResolveSAT, which adds a preprocessing phase to RandomUC. While the running time of ResolveSAT is still exponential, we prove that its running time is smaller than previous algorithms for satisfiability. For the important case of 3-CNF formulae, we show that its running time is at most 2${\cdot}\sp{446n}$. Turning to circuit complexity, we prove lower bounds on the size of depth-3 circuits of unbounded fanin AND and OR gates which compute specific Boolean functions. Since such circuits are composed of depth-2 CNF subcircuits, the characterizations developed in analyzing satisfiability algorithms allow us to bound the contribution of each subcircuit. Using this approach, we show tight lower bounds on the size of such circuits computing the parity function and even stronger lower bounds for certain functions based on error-correcting codes. In addition, inspired by ideas used in polynomial-time algorithms for the satisfiability of 2-CNFs, we obtain strongly exponential lower bounds on the size of depth-3 circuits with bottom fanin 2. We conclude by examining k-CNFs directly in an attempt to identify the formulae which give rise to difficult satisfiability problems. We show that any k-CNF can be written as the union of several sparse k-CNFs, meaning k-CNFs with O(n) clauses. This implies that such sparse formulae are the hard instances, since any other instances can be reduced to them. In addition, this technique allows us to restructure depth-3 circuits with limited bottom fanin, improving counting arguments showing the existence of hard functions.