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

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

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



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






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


Зап. научн. сем. ПОМИ, 2001, том 277, страницы 14–46 (Mi znsl1427)  

Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности

М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов

Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН

Аннотация: Данная статья представляет собой обзор современных алгоритмов для задачи пропозициональной выполнимости, в частности, алгоритмов, верхние оценки сложности которых являются наилучшими на текущий момент. Также обсуждаются связанные вопросы: дерандомизация алгоритма Патури, Пудлака, Сакса и Зейна, лемма Вэлианта-Вазирани и алгоритмы, основанные на случайных блужданиях с “кнопкой возврата”. Библ. – 47 назв.

Полный текст: PDF файл (353 kB)

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2003, 118:2, 4948–4962

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

УДК: 510.52
Поступило: 15.01.2001

Образец цитирования: М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб., 2001, 14–46; J. Math. Sci. (N. Y.), 118:2 (2003), 4948–4962

Цитирование в формате AMSBIB
\RBibitem{VseHirDan01}
\by М.~А.~Всемирнов, Э.~А.~Гирш, Е.~Я.~Данцин, С.~В.~Иванов
\paper Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности
\inbook Теория сложности вычислений.~VI
\serial Зап. научн. сем. ПОМИ
\yr 2001
\vol 277
\pages 14--46
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl1427}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1865895}
\zmath{https://zbmath.org/?q=an:1074.68577}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2003
\vol 118
\issue 2
\pages 4948--4962
\crossref{https://doi.org/10.1023/A:1025645221773}


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

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. В. Баргачев, “Некоторые свойства независимых относительно минимума семейств и групп перестановок”, Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ПОМИ, СПб., 2004, 30–41  mathnet  mathscinet  zmath; V. Bargachev, “On some properties of min-wise independent families and groups of permutations”, J. Math. Sci. (N. Y.), 134:5 (2006), 2340–2345  crossref
    2. А. С. Куликов, С. С. Федин, “Автоматические доказательства верхних оценок на время работы алгоритмов расщепления”, Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ПОМИ, СПб., 2004, 111–128  mathnet  mathscinet  zmath; A. S. Kulikov, S. S. Fedin, “Automated proofs of upper bounds on the running time of splitting algorithms”, J. Math. Sci. (N. Y.), 134:5 (2006), 2383–2391  crossref
    3. Fedin S.S., Kulikov A.S., “Automated proofs of upper bounds on the running time of splitting algorithms”, Parameterized and Exact Computation, Proceedings, Lecture Notes in Computer Science, 3162, 2004, 248–259  crossref  zmath  isi
    4. Vsemirnov M., “Automorphisms of projective spaces and min-wise independent sets of permutations”, SIAM J. Discrete Math., 18:3 (2005), 592–607  crossref  mathscinet  zmath  isi  scopus
    5. Hirsch E.A., Kojevnikov A., “UnitWalk: a new SAT solver that uses local search guided by unit clause elimination”, Ann. Math. Artif. Intell., 43:1-4 (2005), 91–111  crossref  mathscinet  zmath  isi  elib
    6. А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118  mathnet  mathscinet  zmath; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  crossref  isi
    7. Колоколов А.А., Адельшин А.В., Ягофарова Д.И., “Решение задачи выполнимости с использованием метода перебора L-классов”, Информационные технологии, 2009, № 2, 54–59  elib
    8. В. В. Быкова, “Об асимптотике решений рекуррентных соотношений в анализе алгоритмов расщепления для пропозициональной выполнимости”, ПДМ. Приложение, 2013, № 6, 112–116  mathnet
    9. В. В. Быкова, “Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана–Люкхардта”, ПДМ, 2013, № 4(22), 56–66  mathnet
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:418
    Полный текст:137

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