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

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