ПРИМЕНЕНИЕ ЗАДАЧИ SAT ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ
Статья посвящена анализу и классификации способов решения задачи SAT, как точных, так и приближенных. Приведены наилучшие из известных верхних оценок временной сложности алгоритмов-решателей задачи SAT в наихудшем случае, т. е. верхние оценки сложности алгоритмов. Проанализированы практические области применения задачи SAT. Сформулированы некоторые практические задачи в терминах задачи SAT. Рассмотрен пример сведения 3-раскраски графа к SAT, а также подробно изложен алгоритм ее решения.