|
Записки научных семинаров ПОМИ, 2001, том 277, страницы 14–46
(Mi znsl1427)
|
|
|
|
Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)
Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН
Аннотация:
Данная статья представляет собой обзор современных алгоритмов для задачи пропозициональной выполнимости, в частности, алгоритмов, верхние оценки сложности которых являются наилучшими на текущий момент. Также обсуждаются связанные вопросы: дерандомизация алгоритма Патури, Пудлака, Сакса и Зейна, лемма Вэлианта-Вазирани и алгоритмы, основанные на случайных блужданиях с “кнопкой возврата”. Библ. – 47 назв.
Поступило: 15.01.2001
Образец цитирования:
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб., 2001, 14–46; J. Math. Sci. (N. Y.), 118:2 (2003), 4948–4962
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl1427 https://www.mathnet.ru/rus/znsl/v277/p14
|
Статистика просмотров: |
Страница аннотации: | 597 | PDF полного текста: | 308 |
|