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
Abstract
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.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 10
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 12
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 1999
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}