信息学奥林匹克论文

华中师大一附中

赵爽

 1/3 

2-SAT

解法浅析

华中师大一附中 

赵爽 

SAT

理论基础

设

{

}

1

2

,

,

,

n

B

b

b

b

=

"

为一个有限布尔变量集，

{

}

1

2

1

2

ˆ

,

,

,

,

,

,

,

n

n

B

b

b

b

b

b

b

=

¬

¬

"

"

¬

。

设

B

′

是

ˆ

B

的非空子集，定义

b

B

B

b

′

∈

′

∨

=

∨

。对于给定的

1

2

ˆ

,

,

,

m

B

B

B

B

′

′

′

∈

"

①

，求

B

，使得

(

)

(

)

(

)

1

2

1

m

B

B

B

′

′

′

∨

∧

∨

∧

∧

∨

=

"

成立的问题，称为

适定性

(Satisfiability)

问题

，简称

SAT

。

特别的，对于给定的

{

}

m

B

′

，如果

{

}

1,2,

,

max

i

i

m

B

k

=

′

=

"

，我们就把这个问题称为

k-

适定性

问题

，简称

k-SAT

。

可以证明，当

时，

k-SAT

是

NP

完全的。下面我们要讨论的，是

时的情况。

2

k

>

2

k

=

2-SAT 

在

2-SAT

中，

i

B

′

只有两种形式，一种是单个布尔变量

ˆ

x

B

∈

，另一种是两个布尔变量

的或：

(

ˆ

,

)

x

y

x

y

B

∨

∈

。为了方便，我们先分析只存在后一种形式的情况。

我们可以构造有向图

G

。

包含

个顶点，代表

G

2

n

ˆ

B

中的

2

个元素。我们的问题转化

为从

G

中选出

个顶点，使其满足

2-SAT

的条件——当然，代表

和

n

n

i

b

i

b

¬

的顶点不能同时

被选择。下面我们分析一下

i

B

x

y

′

=

∨

在图对应什么。

显然，

(

)

x

y

x

∨

=

¬

¬

∧

¬

y

。这也就是说，如果我们选中

x

¬

，那么我们必须选择

y

；

同样的，如果我们选中

，那么我们必须选择

。因此，对于

y

¬

x

i

B

x

y

′

=

∨

，我们可以在

G

中增加弧

(

)

,

x

y

¬

和

(

)

,

y

x

¬

②

。

①

在下文中，

简写作

{

。

1

,

,

n

X

X

"

}

n

X

②

这里，

,

,

,

x

y

x

y

¬

¬

都表示

G

中代表它们的顶点。下同。