Circuits, cnfs, and satisfiability

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