物理

浅谈 2-SAT 问题

作为一个经常水坛的人，也来发发学术帖

引子

n-SAT 问题，中文为“可存在性问题”

定义是：

给出若干逻辑表达式，要证明有解（一般情况下会让你给出一组解）

（逻辑表达式由 与 或 非 这三种符号和若干逻辑变量组成）

（逻辑变量，值为0或1）

在 n-SAT 问题中

每个逻辑表达式都含有n个逻辑变量，且最终值都为1，且运算符皆为“或”

2-SAT 问题就是 n-SAT 问题的一个子命题（n取2）

求解

我们需要挨个对表达式进行处理

先画一个图，设逻辑变量总数为 k，则该图共有 2k 个节点，分别为a=0，a=1，b=0……（a，b等皆为逻辑变量的变量名）

很简单的思路：若一个变量的取值为0（在进行“非”运算后），则另一变量取值定为1

对于a∨b，按照刚刚的思路

在前文所述的图中，我们连从a=0到b=1和从b=0到a=1共两条有向边

从x到y的有向边 代表 由x可推导得到y

按照如上步骤处理完表达式，我们会得到一个有向图

寻找该图中所有闭环，若有环同时包括了 x=0 和 x=1 这两个点，则无解，反之有解（x为任意题中的逻辑变量）

若从 x=0 经过若干条边能够抵达 x=1，则x的值必定1，反之同理

在确定某一变量的取值后，应沿我们之前作下的有向边，确定一部分变量的取值

若最终仍无法确定取值，则说明其可取任意值

延伸

P问题，代表该问题可在 多项式时间复杂度 范围内解决

NP问题，代表该问题可在 多项式时间复杂度 范围内验证答案的正确性

NPC问题，代表所有的NP问题可归结于该问题

世界上第一个被证明的NPC问题就是 n-SAT问题 （n>3）