Новые верхние оценки для задачи максимальной выполнимости

В работе приводятся сравнительно простые доказательства следующих новых верхних оценок для задач максимальной выполнимости:
$c^N$, где константа $c<2$, а $N$ – число переменных, для задачи MAX-SAT для формул константной плотности;
$2^{K/6}$, где $K$ – число клозов, для задачи MAX-2-SAT;
$2^{N/6,7}$ для задачи $(n,3)$-MAX-2-SAT.
Все оценки доказаны методом расщепления. Основными использующимися идеями являются техника запоминания клозов и использование комбинированных мер сложности.
Работа первого автора поддержана Российским фондом фундаментальных исследований, гранты 06–01–00502а и 08–01–00640а, и Фондом содействия отечественной науке.