Satisfiability coding lemma

In this paper, we prove a lemma that shows how to encode satisfying solutio ns of a k-CNF (boolean formulae in conjunctive normal form with at most k l iterals per clause) succinctly. Using this lemma, which we call the satisfi ability coding lemma, we prove tight lower bounds on depth-3 circuits and i mproved upper bounds for the k-SAT problem. We show an Omega(n(1/4)2 root(n )) lower bound on the size of depth-3 circuits of AND, OR, NOT gates comput ing the parity function. This bound is tight up to a constant factor. We al so present and analyze two simple algorithms for finding satisfying assignm ents of k-CNFs. The first is a randomized algorithm which, with probability approaching 1, finds a satisfying assignment of a satisfiable k-CNF formul a F in time O (n(2)\F\(2n-n/k)). The second algorithm is deterministic, and its running time approaches 2(n-n/2k) for large n and k. The randomized al gorithm improves on previous algorithms for k > 3, though subsequent algori thms improve on it; the deterministic algorithm is the best known determini stic algorithm for k > 4.