Аннотация:
Данная статья представляет собой обзор современных алгоритмов для задачи пропозициональной выполнимости, в частности, алгоритмов, верхние оценки сложности которых являются наилучшими на текущий момент. Также обсуждаются связанные вопросы: дерандомизация алгоритма Патури, Пудлака, Сакса и Зейна, лемма Вэлианта-Вазирани и алгоритмы, основанные на случайных блужданиях с “кнопкой возврата”. Библ. – 47 назв.
Образец цитирования:
М. А. Всемирнов, Э. А. Гирш, Е. Я. Данцин, С. В. Иванов, “Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности”, Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб., 2001, 14–46; J. Math. Sci. (N. Y.), 118:2 (2003), 4948–4962
\RBibitem{VseHirDan01}
\by М.~А.~Всемирнов, Э.~А.~Гирш, Е.~Я.~Данцин, С.~В.~Иванов
\paper Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности
\inbook Теория сложности вычислений.~VI
\serial Зап. научн. сем. ПОМИ
\yr 2001
\vol 277
\pages 14--46
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl1427}
\mathscinet{http://mathscinet.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}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl1427
https://www.mathnet.ru/rus/znsl/v277/p14
Эта публикация цитируется в следующих 12 статьяx:
Peter Jonsson, Victor Lagerkvist, “An initial study of time complexity in infinite-domain constraint satisfaction”, Artificial Intelligence, 245 (2017), 115
Peter Jonsson, Victor Lagerkvist, Lecture Notes in Computer Science, 9255, Principles and Practice of Constraint Programming, 2015, 183
В. В. Быкова, “Об асимптотике решений рекуррентных соотношений в анализе алгоритмов расщепления для пропозициональной выполнимости”, ПДМ. Приложение, 2013, № 6, 112–116
В. В. Быкова, “Об асимптотике решений рекуррентных соотношений специального вида и технике Кульмана–Люкхардта”, ПДМ, 2013, № 4(22), 56–66
А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183
Колоколов А.А., Адельшин А.В., Ягофарова Д.И., “Решение задачи выполнимости с использованием метода перебора L-классов”, Информационные технологии, 2009, № 2, 54–59
Vsemirnov M., “Automorphisms of projective spaces and min-wise independent sets of permutations”, SIAM J. Discrete Math., 18:3 (2005), 592–607
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
Edward A. Hirsch, Arist Kojevnikov, “UnitWalk: A new SAT solver that uses local search guided by unit clause elimination”, Ann Math Artif Intell, 43:1-4 (2005), 91
В. Баргачев, “Некоторые свойства независимых относительно минимума семейств и групп перестановок”, Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ПОМИ, СПб., 2004, 30–41; V. Bargachev, “On some properties of min-wise independent families and groups of permutations”, J. Math. Sci. (N. Y.), 134:5 (2006), 2340–2345
А. С. Куликов, С. С. Федин, “Автоматические доказательства верхних оценок на время работы алгоритмов расщепления”, Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ПОМИ, СПб., 2004, 111–128; 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
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
Цитирование в формате AMSBIB
Обратная связь: