Follow Us :

Dynamic Programming 14

0. Consider the decision problem 2CNFSAT defined as follows:
{Φ|Φ is a satisfiable propositional formula in CNF with at most two literals per clause}
For example, Φ = (x1 ∨ x2) ∧ (x1 ∨ x3) ∧ (x2 ∨ x4) 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.
Cancel reply
Cancel reply