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.
Similar content being viewed by others
References
J. Chen and I. Kanj, “Improved exact algorithms for Max-Sat,” Lect. Notes Comput. Sci., 2286, 98–119 (2002).
T. Hertli, “3-SAT faster and simpler - Unique-SAT bounds for PPSZ hold in general,” arXiv:1103.2165.
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.
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).
A. Kulikov, “Automated generation of simplification rules for SAT and MAXSAT,” Lect. Notes Comput. Sci., 3569, 43–59 (2005).
V. Raman, B. Ravikumar, and S. Srinivasa Rao, “A simplified NP-complete MAXSAT problem,” Inform. Process. Lett., 65, No. 1, 1–6 (1998).
J. Edmonds, “Paths, trees, and flowers,” in: Modern Birkhäuser Classics, Birkhäuser, Boston (1987), pp. 361–379.
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).
D. Scheder, “Guided search and a faster deterministic algorithm for 3-SAT,” Lect. Notes Comput. Sci., 4957, 60–71 (2008).
R. Williams, “A new algorithm for optimal 2-constraint satisfaction and its implications,” Theoret. Comput. Sci., 348, No. 2, 357–365 (2005).
A. Kulikov and K. Kutzkov, “New bounds for MAX-SAT by clause learning,” Lect. Notes Comput. Sci., 4649, 194–204 (2007).
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).
M. Wahlström, “An algorithm for the SAT problem for formula of linear length,” Lect. Notes Comput. Sci., 3669, 107–118 (2005).
Author information
Authors and Affiliations
Corresponding author
Additional information
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 399, 2012, pp. 5–14.
Rights 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
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-012-1101-z