## 2-SAT problem

Moderator: Board moderators

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

### 2-SAT problem

http://acm.tju.edu.cn/toj/showp2506.html

it is a 2-SAT problem. i have faced such a problem first time in life. can any one please tell me how to solve it in polynomial time?
Self judging is the best judging!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Write the boolean formula as a conjunction of implications (e.g. (x1->x2)^(~x1->x3)), and create a graph whose vertices are xi and ~xi for all variables xi, and whose edges are the implications. The formula is satisfiable if and only if no contradiction of the form xi -> ~xi -> xi arises following a chain of such implications. This amounts to checking whether xi and ~xi are in the same strongly connected component, which can be done in linear time.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

but i am not yet fully clear.

u mean: implication= x1->x2
and cunjunction as: (x1->x2) AND (!x1 -> x3)

that means, implication = OR and cunjuntction = AND ?

and, the edges are directed or non directed?

Can you please give me an example of the process?

Thanks again
Self judging is the best judging!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### Re: 2-SAT problem

The express (a or b) is equivalent to ~a --> b and also ~b --> a, and in fact the 2 equations together capture all there is in the expression a or b. Thus build a graph of size 2n (where n is the number of variables), then for each expression (a or b) construct two directed edges accordingly. There is a contradiction if, for some variable x, there is a path from x to ~x AND a path from ~x to x. Otherwise the instance is a yes instance