2−SAT 问题

· · 个人记录

\color{blue}\texttt{2-SAT}

2−SAT，即布尔方程在两元限制下的求合法解问题。

一般模型

每个单位有非 a 即 b 的两种取值，而有些单位之间有取值的制约关系。要求给出一组合法解。

做法

制约关系间建图。如果图上一个节点 u 可以到达另一个节点 v，代表着如果 u 被取到，v 一定被取到。

一般的方法是：若单位 x 不能取 X_1，那么只能取 X_2。因此我们可以将每个限制转换成，若单位 i 取 a，单位 j 必须取 b 的形式，接着给 i.a 与 j.b 之间连接一条有向边。

很显然，对于每个强联通分量，要么都取，要么都不取。于是我们求强联通分量即可。

解的存在性

如果同一个单位的两个取值在同一个强联通分量内，一定无解。否则一定有解。

输出方案

唯一可能存在的冲突在于，如果同一个单位的点 i.a 指向了 i.b，那么 i 只能选择 i.b，如果选了 i.a，会因为可以推出 i.b 而不满足。因此每个单位都要选拓扑序靠后的点。

如果强联通分量的编号小，意味着它先出栈，离根节点的距离远，拓扑序上靠后。所以对于每个 i\in [1,n]，取 I_1,I_2 中其存在的强联通分量编号小的即可。

\color{blue}\texttt{k-SAT}

对于 k>2 的情况，是 NP 完全问题。