2-SAT

**2-КНФ** — КНФ, в которой каждый клоз состоит из двух литералов. Задача выполнимости для таких формул называется **2-SAT**. Формула $l_1 \lor l_2$ эквивалентна импликациям $\bar{l}_1 \to l_2$ и $\bar{l}_2 \to l_1$. **Граф импликаций** $G(F)$ строится следующим образом: 1. Вершины — литералы из формулы $F$. 2. Каждому клозу $l_1 \lor l_2$ сопоставляются ориентированные ребра $(\bar{l}_1, l_2)$ и $(\bar{l}_2, l_1)$.

Раскраска $\phi$ графа импликаций в цвета $\{0, 1\}$ называется **булевой**, если: 1. $\forall{l}\mathpunct{:}~ \phi(l) \neq \phi(\bar{l})$ 2. $\forall{\text{ребра } (l_1, l_2)}\mathpunct{:}~ \phi(l_2) \ge \phi(l_1)$ Из свойства (2) по транзитивности следует: если $l_2$ достижима из $l_1$, то $\phi(l_2) \ge \phi(l_1)$.

Существует булева раскраска $G(F)$ $\iff$ не существует переменной $x$, для которой вершины $x$ и $\bar{x}$ взаимно достижимы в $G(F)$ (лежат в одной компоненте сильной связности).

$\Large{\implies}$ (Необходимость) Если существует $x$ такая, что $x$ и $\bar{x}$ взаимно достижимы, то по свойству транзитивности $\phi(x) \ge \phi(\bar{x})$ и $\phi(\bar{x}) \ge \phi(x)$. Это влечет $\phi(x) = \phi(\bar{x})$, что нарушает первое условие булевой раскраски. $\Large{\impliedby}$ (Достаточность) Разобьем $G(F)$ на компоненты сильной связности и выполним их топологическую сортировку. По условию $x$ и $\bar{x}$ лежат в разных компонентах. Определим раскраску: $\phi(x) = 1$, если $comp(x) > comp(\bar{x})$ (в порядке топологической сортировки), иначе $\phi(x) = 0$. Условие $\phi(x) \neq \phi(\bar{x})$ выполнено. Предположим, что существует ребро $(l_1, l_2)$, нарушающее условие (т.е. $\phi(l_1)=1, \phi(l_2)=0$). Тогда: $$comp(l_1) > comp(\bar{l}_1) \text{ и } comp(l_2) < comp(\bar{l}_2)$$ Из существования ребра $(l_1, l_2)$ следует существование ребра $(\bar{l}_2, \bar{l}_1)$. Свойства порядка компонент приводят к противоречию. Значит, раскраска корректна. $\square$

Задача 2-SAT может быть решена за время $O(\ell)$, где $\ell$ — число клозов в формуле.

Алгоритм решения: 1. Построить граф $G(F)$ (содержит $2\ell$ ребер). 2. Найти компоненты сильной связности (например, алгоритмом Тарьяна или Косарайю) и отсортировать их топологически. Это занимает линейное время. 3. Если $\exists{x}\mathpunct{:}~ comp(x) = comp(\bar{x})$, вернуть 0 (решения нет). 4. Иначе построить булеву раскраску по правилу из критерия выполнимости и вернуть результат. Все шаги требуют времени $O(\ell)$. $\square$