License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.237
URN: urn:nbn:de:0030-drops-30147
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3014/
Go to the corresponding LIPIcs Volume Portal

Hertli, Timon ; Moser, Robin A. ; Scheder, Dominik

Improving PPSZ for 3-SAT using Critical Variables

pdf-format:
24.pdf (0.7 MB)

Abstract

A critical variable of a satisfiable CNF formula is a variable that has the same value in all satisfying assignments. Using a simple case distinction on the fraction of critical variables of a CNF formula, we improve the running time for 3-SAT from O(1.32216^n) [Rolf 2006] to O(1.32153^n). Using a different approach, Iwama et al. very recently achieved a running time of O(1.32113^n). Our method nicely combines with theirs, yielding the currently fastest known algorithm with running time O(1.32065^n). We also improve the bound for 4-SAT from O(1.47390^n) [Hofmeister et al. 2002] to O(1.46928^n), where O(1.46981^n) can be obtained using the methods of Hofmeister and Rolf.

BibTeX - Entry

@InProceedings{hertli_et_al:LIPIcs:2011:3014,
  author =	{Timon Hertli and Robin A. Moser and Dominik Scheder},
  title =	{{Improving PPSZ for 3-SAT using Critical Variables}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{237--248},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3014},
  URN =		{urn:nbn:de:0030-drops-30147},
  doi =		{10.4230/LIPIcs.STACS.2011.237},
  annote =	{Keywords: SAT, satisfiability, randomized, exponential time, algorithm, 3-SAT, 4-SAT}
}

Keywords: SAT, satisfiability, randomized, exponential time, algorithm, 3-SAT, 4-SAT
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI