Guided Search and a Faster Deterministic Algorithm for 3-SAT | SpringerLink
Skip to main content
Springer Nature Link
Log in

Guided Search and a Faster Deterministic Algorithm for 3-SAT

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

Most deterministic algorithms for NP-hard problems are splitting algorithms: They split a problem instance into several smaller ones, which they solve recursively. Often, the algorithm has a choice between several splittings. For 3-SAT, we show that choosing wisely which splitting to apply, one can avoid encountering too many worst-case instances. This improves the currently best known deterministic worst case running time for 3-SAT from \(\mathcal{O}(1.473^n)\) to \(\mathcal{O}(1.465^n)\), n being the number of variables in the input formula.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Beigel, R., Eppstein, D.: 3-coloring in time O(1.3446n): a no-MIS algorithm. In: Proc. 36th Symp. Foundations of Computer Science, October 1995, pp. 444–453. IEEE, Los Alamitos (1995)

    Google Scholar 

  2. Brueggemann, T., Kern, W.: An improved local search algorithm for 3-SAT. Memorandum 1709, Department of Applied Mathematics, University of Twente, Enschede (2004)

    Google Scholar 

  3. Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, O., Schöning, U.: A deterministic (2 − 2/(k + 1))n algorithm for k-SAT based on local search. Theoretical Computer Science 289, 69–83 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  4. Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Comm. ACM 5, 394–397 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  5. Davis, M., Putnam, H.: A computing procedure for quantification theory. J. Assoc. Comput. Mach. 7, 201–215 (1960)

    MATH  MathSciNet  Google Scholar 

  6. Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 287–295 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  7. Rolf, D.: Improved bound for the PPSZ/Schöning-algorithm for 3-SAT. Electronic Colloquium on Computational Complexity (ECCC) 159 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Theoretical Computer Science, ETH Zürich, CH-8092, Zürich, Switzerland

    Dominik Scheder

Authors
  1. Dominik Scheder
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Scheder, D. (2008). Guided Search and a Faster Deterministic Algorithm for 3-SAT. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation