2SAT
Рассмотрим функцию, записанную в виде 2-КНФ (КНФ Крома).
| Определение: |
| 2-SAT выполнимость данной функции — эта задача распределения аргументов таким образом, чтобы результат данной функции был равен 1. |
Алгоритм Решения
Рассмотрим любой дизъюнкт функции:
Несложно заметить, что это равнозначно записи
Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: и для каждого дизъюнкта функции
Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной из вершины нельзя достичь и из вершины нельзя достичь одновременно.
Доказательство
Пусть 2-SAT имеет решение.
Докажем, что не может быть такого, чтобы для любой переменной из вершины можно достичь и из вершины можно достичь одновременно.
Тогда чтобы из достичь было верным), должен быть равен 1. С другой стороны для того, чтобы из достичь было верным), должен быть равен 0. Отсюда следует противоречие.
Пусть для любой переменной из вершины нельзя достичь и из вершины нельзя достичь одновременно.
Докажем, что этого достаточно, чтобы 2-SAT имело решение.
Пусть из можно достичь , но из вершины нельзя достичь . Докажем, что из не достижимо такой , что из достижимо . (т.е. .
Если из , то , отсюда следует . Тогда . Следовательно . Противоречие.
