Задачи SAT и 3-SAT
Допустим, имеется множество X из n булевых переменных x1, …, xn; каждая переменная может принимать значение 0 или 1 (эквиваленты false и true).
Литералом по X называется одна из переменных xi или ее отрицание. Наконец, условием называется обычная дизъюнкция литералов. (Еще раз: все). Мы говорим, что условие имеет длину , если оно содержит литералов.
А теперь дадим формальное определение присваиванию значений, удовлетворяющих набору условий. Логическим присваиванием для X называется присваивание значения 0 или 1 каждому xi; другими словами, это функция ν : X → {0,1}.
Присваивание v неявно задает значение истинности, противоположное xi. Присваивание выполняет условие C, если после него C дает результат 1 по условиям булевой логики; это эквивалентно требованию о том, чтобы по крайней мере один из литералов в C имел значение 1.
Присваивание выполняет совокупность условий C1, …, Ck, если в результате его все Ci дают результат 1; иначе говоря, если в результате его конъюнкция C1 ҍ C2 ҍ … ҍ Ck дает результат 1. В этом случае v называется выполняющим присваиванием в отношении , а набор условий называется выполнимым.
Рассмотрим простой пример. Допустим, имеются три условия:
Теперь можно привести формулировку задачи выполнимости, также обозначаемой SAT:
Для заданного множества условий C1, ..., Ck по множеству переменных
X = {x1, …, xn} существует ли выполняющее логическое присваивание?
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу