DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2017.9

PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster

Authors: Dominik Scheder and John P. Steinberger

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract

The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify Hertli's analysis for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. Combining this with a result by Hertli from 2014, in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.

Cite as

Dominik Scheder and John P. Steinberger. PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{scheder_et_al:LIPIcs.CCC.2017.9,
  author =	{Scheder, Dominik and Steinberger, John P.},
  title =	{{PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.9},
  URN =		{urn:nbn:de:0030-drops-75355},
  doi =		{10.4230/LIPIcs.CCC.2017.9},
  annote =	{Keywords: Boolean satisfiability, exponential algorithms, randomized algorithms}
}

Search Results

Documents authored by Steinberger, John P.

PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster

Abstract

Cite as

Thanks for your feedback!

Could not send message