Consider the decision problem $2CNFSAT$ defined as follows: $\Phi \mid \Phi$ is a satisfiable propositional formula in CNF with at most two literals per clause For example, $\Phi = (x_1 \vee x_2) \wedge (x_1 \vee \overline{x_3}) \wedge (x_2 \vee x_4)$ is a Boolean formula and it is in $2CNFSAT$. The decision problem $2CNFSAT$ is (A) NP-Complete. (B) solvable in polynomial time by reduction to directed graph reachability. (C) solvable in constant time since any input instance is satisfiable. (D) NP-hard, but not NP-complete.

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 (A) NP-Complete. (B) solvable in polynomial time by reduction to directed graph reachability. (C) solvable in constant time since any input instance is satisfiable. (D) NP-hard, but not NP-complete.

Topic-wise GATE CS PYQs with verified steps