Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
It is still not known whether the satisfiability problem (SAT), and hence the maximum satisdiability problem (MAX-SAT), can be solved in time poly({pipe}F{pipe})cn for c < 2, where c is a constant, n is the number of variables, and F is the input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximum number of variable occurrences, or the length of the formula is bounded. In this paper, we consider the (n, 3)-MAX-SAT problem-the 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*(2n/3). As a byproduct, we also obtain a polynomially sovable subclass that may be of independent interest. Bibliography: 13 titles.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 1-6 |
Число страниц | 6 |
Журнал | Journal of Mathematical Sciences (United States) |
Том | 188 |
Номер выпуска | 1 |
DOI | |
Состояние | Опубликовано - 1 янв 2013 |
ID: 49788084