Geodesic
A new upper bound for $(n,3)$-MAX-SAT
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 5-14 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

It is still not known whether the satisfiability problem (SAT), and hence maximum satisfiability problem (MAX-SAT), can be solved in time $\operatorname{poly}(|F|)c^n$, for $c<2$, where $c$ is a constant, $n$ is the number of variables, and $F$ is an input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximal number of variable occurrences or the length of the formula is bounded. In this paper, we consider the $(n,3)$-MAX-SAT problem – a 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^*(2^{n/3})$. As a byproduct we also obtain a polynomially solvable subclass that may be of independent interest. 
@article{ZNSL_2012_399_a0,
     author = {I. A. Bliznets},
     title = {A new upper bound for $(n,3)${-MAX-SAT}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {5--14},
     year = {2012},
     volume = {399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a0/}
}
TY  - JOUR
AU  - I. A. Bliznets
TI  - A new upper bound for $(n,3)$-MAX-SAT
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 5
EP  - 14
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a0/
LA  - en
ID  - ZNSL_2012_399_a0
ER  - 
%0 Journal Article
%A I. A. Bliznets
%T A new upper bound for $(n,3)$-MAX-SAT
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 5-14
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a0/
%G en
%F ZNSL_2012_399_a0
I. A. Bliznets. A new upper bound for $(n,3)$-MAX-SAT. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 5-14. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a0/

[1] J. Chen, I. Kanj, “Improved exact algorithms for Max-Sat”, Lect. Notes Computer Sci., 2286, 2002, 98–119 | DOI | MR

[2] H. Timon, 3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General, 2011, arXiv: 1103.2165 | MR

[3] R. A. Moser, D. Scheder, “A full derandomization of Schöning's $k$-SAT algorithm”, Proceedings of the 43rd annual ACM Symposium on Theory of Computing, San Jose, California, USA, 2011, 245–252 | MR | Zbl

[4] S. S. Fedin, A. S. Kulikov, “Automated proofs of upper bounds on the running time of splitting algorithms”, Lect Notes Computer Sci., 3162, Springer, 2004, 248–259 | DOI | Zbl

[5] A. Kulikov, “Automated generation of simplification rules for SAT and MAXSAT”, Lect Notes Computer Sci., 3569, Springer, 2005, 43–59 | MR

[6] Venkatesh Raman, B. Ravikumar, S. Srinivasa Rao, “A simplified NP-complete MAXSAT problem”, Information Processing Lett., 65:1 (1998), 1–6 | DOI | MR

[7] J. Edmonds, “Paths, Trees, and Flowers”, Modern Birkhäuser Classics, Birkhüser Boston, 1987, 361–379

[8] E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning, “A deterministic $(2-2/(k+1))^n$ algorithm for $k$-SAT based on local search”, Theor. Computer Sci., 289:1 (2002), 69–83 | DOI | MR | Zbl

[9] D. Scheder, “Guided search and a faster deterministic algorithm for 3-SAT”, Lect. Notes Computer Sci., 4957, Springer, Berlin–Heidelberg, 2008, 60–71 | DOI | MR | Zbl

[10] W. Ryan, “A new algorithm for optimal 2-constraint satisfaction and its implications”, Theor. Computer Sci., 348:2 (2005), 357–365 | DOI | MR | Zbl

[11] A. Kulikov, K. Kutzkov, “New bounds for MAX-SAT by Clause Learning”, Lect. Notes Computer Sci., 4649, Springer, Berlin–Heidelberg, 2007, 194–204 | DOI | Zbl

[12] E. Dantsin, A. Wolpert, “MAX-SAT for formulas with constant Clause density can be solved faster than in $O^*(2^n)$ time”, Lect. Notes Computer Sci., 4121, Springer, Berlin–Heidelberg, 2006, 266–276 | DOI | MR | Zbl

[13] W. Magnus, “An algorithm for the SAT problem for formulae of linear length”, Lect. Notes Computer Sci., 3669, Springer, Berlin–Heidelberg, 2005, 107–118 | DOI | MR | Zbl