Chicago Journal of Theoretical Computer Science

Volume 1999

Article 11

Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

Satisfiability Coding Lemma

Ramamohan Paturi (University of California San Diego), Pavel Pudlak (Math. Institute, Academy of Sciences, Czech Republic), and Francis Zane (ATT Bell Laboratories)
31 December 1999

In this paper, we prove a lemma that shows how to encode satisfying solutions of a k-CNF (boolean formulae in conjunctive normal form with at most k literals per clause) succinctly. Using this lemma, which we call the satisfiability coding lemma, we prove tight lower bounds on depth-3 circuits and improved upper bounds for the k-SAT problem. We show an Omega(n^{1/4}2^{\sqrt{n}}) lower bound on the size of depth-3 circuits of AND, OR, NOT gates computing the parity function. This bound is tight up to a constant factor. We also present and analyze two simple algorithms for finding satisfying assignments of k-CNFs. The first is a randomized algorithm which, with probability approaching 1, finds a satisfying assignment of a satisfiable k-CNF formula F in time O(n^2 |F| 2^{n-n/k}). The second algorithm is deterministic, and its running time approaches 2^{n-n/2k} for large n and k. The randomized algorithm improves on previous algorithms for k>3, though subsequent algorithms improve on it; the deterministic algorithm is the best known deterministic algorithm for k>4.

DOI: 10.4086/cjtcs.1999.011
[] Article 10 [] Article 12
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Sat Mar 20 09:32:31 CST 1999