Computer Sciences > GATE 2014 SET-3 > Complexity Theory
Consider 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
{Φ | Φ 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
Correct : b
Total Unique Visitors
Loading......