Dynamic Programming 14

56Consider the decision problem 2CNFSAT defined as follows:
{Φ|Φ is a satisfiable propositional formula in CNF with at most two literals per clause}
For example, Φ = (x₁ ∨ x₂) ∧ (x₁ ∨ x₃) ∧ (x₂ ∨ x₄) is a Boolean formula and it is in 2CNFSAT. The" decision problem 2CNFSAT is

Option : B
Explanation :
2CNF SAT can be solvable in polynomial time by reduction to directed graph reach ability.

Forgot your password?

I agree with the Terms.