# 2-clause satisfiability associated graph

A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:

2-SAT: Input : A conjunction $\Phi$ of 2-clauses. Question : Is it satisfisable?

For each set of 2-clause $C$ we associate $G_C$ defined as

• $V_{G_C}$ contains two vertices $x$ and $\neg x$ for each variables in $C$.
• $E_{G_C}$ contains an edge $\alpha \rightarrow \beta$ if and only if $\neg \alpha \vee\beta$ or $\beta \vee\neg\alpha$ is in $C$.

This graph should help me show this problem belongs to P. Yet,

• Why is $C$ satisfiable if and only if $G_C$ doesn't have any loop?
• Why does $G_C$ space is polynomial?
• Why is $G_C$ calculation from $C$ is polynomial?
• This problem is general reference. Where have you looked for explanations? What have you tried towards answering your questions? (Please polish the language some: using multiple verbs per sentence makes them hard to understand.)
– Raphael
Nov 13, 2016 at 9:00
• @Juho As far as we have at each stage 2 possibilites, don't we create $2^n$ possbilities with $n$ the number of 2-clauses? Nov 13, 2016 at 23:13