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?

## 2-SAT problem

**Moderator:** Board moderators

### 2-SAT problem

Self judging is the best judging!

thanks for replying.

but i am not yet fully clear.

u mean: implication= x1->x2

and cunjunction as: (x1->x2)

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

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!

### 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