Skip to main content
Log in

A new upper bound for (n, 3)-MAX-SAT

  • Published:
Journal of Mathematical Sciences Aims and scope Submit manuscript

It is still not known whether the satisfiability problem (SAT), and hence the maximum satisdiability problem (MAX-SAT), can be solved in time poly(|F|)c n for c < 2, where c is a constant, n is the number of variables, and F is the input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximum number of variable occurrences, or the length of the formula is bounded. In this paper, we consider the (n, 3)-MAX-SAT problem-the special case of MAX-SAT where each variable appears in a formula at most three times. We present a simple algorithm with running time O*(2n/3). As a byproduct, we also obtain a polynomially sovable subclass that may be of independent interest. Bibliography: 13 titles.

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

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Chen and I. Kanj, “Improved exact algorithms for Max-Sat,” Lect. Notes Comput. Sci., 2286, 98–119 (2002).

    Article  MathSciNet  Google Scholar 

  2. T. Hertli, “3-SAT faster and simpler - Unique-SAT bounds for PPSZ hold in general,” arXiv:1103.2165.

  3. R. A. Moser and D. Scheder, “A full derandomization of Schöning’s k-SAT algorithm,” in: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (2011), pp. 245–252.

  4. S. S. Fedin and A. S. Kulikov, “Automated proofs of upper bounds on the running time of splitting algorithms,” Lect. Notes Comput. Sci., 3162, 248–259 (2004).

    Article  Google Scholar 

  5. A. Kulikov, “Automated generation of simplification rules for SAT and MAXSAT,” Lect. Notes Comput. Sci., 3569, 43–59 (2005).

    MathSciNet  Google Scholar 

  6. V. Raman, B. Ravikumar, and S. Srinivasa Rao, “A simplified NP-complete MAXSAT problem,” Inform. Process. Lett., 65, No. 1, 1–6 (1998).

    Article  MathSciNet  Google Scholar 

  7. J. Edmonds, “Paths, trees, and flowers,” in: Modern Birkhäuser Classics, Birkhäuser, Boston (1987), pp. 361–379.

    Google Scholar 

  8. E. Dantsin, A. Goerdt, E. A. Hirsh, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, and U. Shöning, “A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search,” Theoret. Comput. Sci., 289, No. 1, 69–83 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  9. D. Scheder, “Guided search and a faster deterministic algorithm for 3-SAT,” Lect. Notes Comput. Sci., 4957, 60–71 (2008).

    Article  MathSciNet  Google Scholar 

  10. R. Williams, “A new algorithm for optimal 2-constraint satisfaction and its implications,” Theoret. Comput. Sci., 348, No. 2, 357–365 (2005).

    Article  MathSciNet  MATH  Google Scholar 

  11. A. Kulikov and K. Kutzkov, “New bounds for MAX-SAT by clause learning,” Lect. Notes Comput. Sci., 4649, 194–204 (2007).

    Article  Google Scholar 

  12. E. Dantsin and A. Wolpert, “MAX-SAT for formulas with constant clause density can be solved faster than in O*(2n) time,” Lect. Notes Comput. Sci., 4121, 266–276 (2006).

    Article  MathSciNet  Google Scholar 

  13. M. Wahlström, “An algorithm for the SAT problem for formula of linear length,” Lect. Notes Comput. Sci., 3669, 107–118 (2005).

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to I. A. Bliznets.

Additional information

Published in Zapiski Nauchnykh Seminarov POMI, Vol. 399, 2012, pp. 5–14.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bliznets, I.A. A new upper bound for (n, 3)-MAX-SAT. J Math Sci 188, 1–6 (2013). https://doi.org/10.1007/s10958-012-1101-z

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10958-012-1101-z

Keywords

Navigation