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

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $c2$, 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},
     publisher = {mathdoc},
     volume = {399},
     year = {2012},
     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
PB  - mathdoc
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
%I mathdoc
%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/