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

До сих пор неизвестно, решаются ли задачи выполнимости или максимальной выполнимости за время $\operatorname{poly}(F)c^n$, для $c<2$, где $c$ – константа, $n$ – число переменных, $F$ – входная формула. Подобные оценки известны, однако, для некоторых частных случаев, когда ограничены длина дизъюнктов, максимальное количество вхождений переменных или длина формулы. В данной работе рассматривается задача $(n,3)$-MAX-SAT – частный случай задачи MAX-SAT, где каждая переменная встречается не более трех раз. Мы представляем простой алгоритм со временем работы $O^*(2^{n/3})$. Также приводится полиномиально разрешимый подкласс формул. Библ. – 13 назв.