RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ПОМИ, 2012, том 399, страницы 5–14 (Mi znsl5218)  

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 назв.

Ключевые слова: алгоритм, максимальная выполнимость, выполнимость.

Полный текст: PDF файл (199 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2013, 188:1, 1–6

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.712.2
Поступило: 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

Цитирование в формате AMSBIB
\RBibitem{Bli12}
\by I.~A.~Bliznets
\paper A new upper bound for $(n,3)$-MAX-SAT
\inbook Теория сложности вычислений.~X
\serial Зап. научн. сем. ПОМИ
\yr 2012
\vol 399
\pages 5--14
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl5218}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2944997}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2013
\vol 188
\issue 1
\pages 1--6
\crossref{https://doi.org/10.1007/s10958-012-1101-z}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84871930916}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl5218
  • http://mi.mathnet.ru/rus/znsl/v399/p5

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:125
    Полный текст:47
    Литература:5

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017