|
Записки научных семинаров ПОМИ, 2012, том 399, страницы 5–14
(Mi znsl5218)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
A new upper bound for $(n,3)$-MAX-SAT
[Новая верхняя оценка для $(n,3)$-MAX-SAT]
I. A. Bliznets St. Petersburg University of the Russian Academy of Sciences, St. Petersburg, Russia
Аннотация:
До сих пор неизвестно, решаются ли задачи выполнимости или максимальной выполнимости за время $\operatorname{poly}(F)c^n$, для $c<2$, где $c$ – константа, $n$ – число переменных, $F$ – входная формула. Подобные оценки известны, однако, для некоторых частных случаев, когда ограничены длина дизъюнктов, максимальное количество вхождений переменных или длина формулы. В данной работе рассматривается задача $(n,3)$-MAX-SAT – частный случай задачи MAX-SAT, где каждая переменная встречается не более трех раз. Мы представляем простой алгоритм со временем работы $O^*(2^{n/3})$. Также приводится полиномиально разрешимый подкласс формул. Библ. – 13 назв.
Ключевые слова:
алгоритм, максимальная выполнимость, выполнимость.
Поступило: 15.01.2012
Образец цитирования:
I. A. Bliznets, “A new upper bound for $(n,3)$-MAX-SAT”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 5–14; J. Math. Sci. (N. Y.), 188:1 (2013), 1–6
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5218 https://www.mathnet.ru/rus/znsl/v399/p5
|
Статистика просмотров: |
Страница аннотации: | 238 | PDF полного текста: | 75 | Список литературы: | 18 |
|