Question

3. Show that there exists a polynomial time algorithm for deciding whether a 2-CNF formula is satisfiable. Hint Note that any clause containing exactly two variables can be written in terms of a conditional, i.e.: Next, look at the directed graph whose nodes are variables (and their negations), and think what happens if there is some cycle containing a variable r and its negation .

Answer 1

let us consider a 2-CNF formula:-

(¬x∨y) ∧(¬y∨z)∧(x∨¬z)∧(z∨y)

where x and y are boolean variables.

and corresponding directed graph is:-

graph consists of 2n (n=number of variables) nodes, "one node for variable and one for negation of that variable" for each distinct variable in formula.

there exists a directed edge (α,β) in G iff there exists a clause ( α V β) in Formula.

we will show how to solve this problem using path searching algos in graph(e.g. breadth first search , depth first search),

since BFS and DFS algos are polynomially bounded.

We have the following efficient polynomial time algorithm for 2-CNF to decide satisfiability:-

1=> For each variable x find if there is a
path from x to ¬x and vice-versa (you are searching for cycle between variable x and its negation ¬x here actually).

2=>if any of these test cases(in first step) gets succeeded (means you hit the cycle), reject it as it then won't be satisfiable.

(hope you know what satisfiability and unsatisfiability is,if not comment out).

3=>Accept otherwise(means you did not get even a single cycle in your graph).

[and hence you get to conclusion whether that your formula is satisfiable in polynomial time as you are using BFS and DFS searching algos to find path in your first step of this algo which are polynomially bounded]

• [A formula is unsatisfiable iff there exists a paths( or you can say cycle between x and ¬x) of the form x..¬x and ¬x..x]