Question

A 2cnf-formula is an AND of clauses, where each clause is an OR of at most two literals. Let . Show that. Show that $\mathbf{2}\mathit{S}\mathit{A}\mathit{T}\mathbf{\in }\mathit{P}$.

Short answer

It can be shown that$2SAT\in P$

Step-by-step solution

Step-1:Explain 2 CNF

If and only if no two complementary literals appear in the same strongly connected component (SCC) of the implication graph, the 2cnf-formula expressed using the implication graph is satisfiable.

Step-2: Show that 2SAT∈P

Given a 2cnf-formula$\varphi$ on variable$x_1,...,x_n$ . Prepare a list of variables that make the clause. If any pair is false then entire formula is unsatisfiable. Else it is satisfiable as all the clauses are connected by $\wedge$are true.

By iterating through each clause in formula and by saving pairs of variables that construct the clause, it can be solved in polynomial time.

On getting the input, then through the saved list it is iterated. If 0 is yielded by any pair on list then it shows that the entire clause is false as all the clause is connected by$\wedge$ .

A 2cnf-formula $\varphi$on the variable $x_1,...,x_n$is given . Make a list of all the variables that make up the clause. If any of the pairs is false, the entire formula will be unsatisfactory. Otherwise, it is acceptable because all of the clauses are connected by$\wedge$true.

It can be solved in polynomial time by iterating through each sentence in the formula and saving the pairs of variables that make up the clause. It is iterated after receiving the input and going through the saved list.

If any pair on the list returns 0, it means that the entire clause is false, as all of the clauses are related by $\wedge$.

Propogate all the “true values” down the paths and the “false values” up the paths.

Thus, the given algorithm never assign both true nad false to the same variable.

The entire algorithm will be executed in polynomial time.

Therefore, it has been shown that $2SAT\in P$.