In a 2cnf-formula, each clause is an OR of at most two terms, and the clauses are combined with ANDs. For example, (x₁ v x₂)^(x₃ V x₄)^(x₁ v x₃) i is a 2 cnf-formula. Define the language 2SAT of satisfiable 2 cnf-formulas:
2SAT = {<ϕ> | is a satisfiable 2cnf-formula }.
Show that 2SAT is in P
