Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

PPSZ for k 5: More Is Better

PPSZ for k 5: More Is Better We show that for k 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k 5, there is a strictly increasing function f: [0,1] R with f(0) = 0 that has the following property. If F is a k-CNF formula over n variables and |sat(F)| = 2 n solutions, then PPSZ finds a satisfying assignment with probability at least 2ck n o(n) + f() n. Here, 2ck n o(n) is the success probability proved by Paturi et al. [11] for k-CNF formulas with a unique satisfying assignment. Our proof rests on a combinatorial lemma: given a set S 0,1 n, we can partition 0,1 n into subcubes such that each subcube B contains exactly one element of S. Such a partition B induces a distribution on itself, via Pr [B] = |B| / 2n for each B B. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (minS: |S| = s maxB H(B)) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

PPSZ for k 5: More Is Better

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/ppsz-for-k-5-more-is-better-hGI9JPGlMv
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3349613
Publisher site
See Article on Publisher Site

Abstract

We show that for k 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k 5, there is a strictly increasing function f: [0,1] R with f(0) = 0 that has the following property. If F is a k-CNF formula over n variables and |sat(F)| = 2 n solutions, then PPSZ finds a satisfying assignment with probability at least 2ck n o(n) + f() n. Here, 2ck n o(n) is the success probability proved by Paturi et al. [11] for k-CNF formulas with a unique satisfying assignment. Our proof rests on a combinatorial lemma: given a set S 0,1 n, we can partition 0,1 n into subcubes such that each subcube B contains exactly one element of S. Such a partition B induces a distribution on itself, via Pr [B] = |B| / 2n for each B B. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (minS: |S| = s maxB H(B)) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Sep 12, 2019

Keywords: Boolean satisfiability

References

  • Improving a probabilistic 3-SAT algorithm by dynamic search and independent clause pairs
    Baumer, Sven; Schuler, Rainer
  • Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability
    Bollobás, Béla
  • The complexity of unique k-SAT: An isolation lemma for k-CNFs
    Calabro, Chris; Impagliazzo, Russell; Kabanets, Valentine; Paturi, Ramamohan
  • 3-SAT faster and simpler—Unique-SAT bounds for PPSZ hold in general
    Hertli, Timon
  • Breaking the PPSZ barrier for unique 3-SAT
    Hertli, Timon
  • Improving PPSZ for 3-SAT using critical variables
    Hertli, Timon; Moser, Robin A.; Scheder, Dominik
  • A probabilistic 3-SAT algorithm further improved
    Hofmeister, Thomas; Schöning, Uwe; Schuler, Rainer; Watanabe, Osamu
  • Improved randomized algorithms for 3-SAT
    Iwama, Kazuo; Seto, Kazuhisa; Takai, Tadashi; Tamaki, Suguru
  • Improved upper bounds for 3-SAT
    Iwama, Kazuo; Tamaki, Suguru
  • {n
    Paturi, Ramamohan
  • An improved exponential-time algorithm for k-SAT
    Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
  • Satisfiability coding lemma
    Paturi, Ramamohan; Pudlák, Pavel; Zane, Francis
  • Improved bound for the PPSZ/Schöning-Algorithm for 3-SAT
    Rolf, Daniel
  • On the density of families of sets
    Sauer, N.
  • PPSZ for general k-SAT—Making Hertli’s analysis simpler and 3-SAT faster
    Scheder, Dominik; Steinberger, John P.
  • A probabilistic algorithm for k-SAT and constraint satisfaction problems
    Schöning, Uwe
  • A combinatorial problem: Stability and order for models and theories in infinitary languages
    Shelah, Saharon