"Записки научных семинаров ПОМИ"

Том 399, стр. 5-14

СПбАУ НОЦНТ РАН, ул. Хлопина, д. 8, корпус 3, Санкт-Петербург 194021, Россия

ivanbliznets@tut.by

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