Consider the decision problem \(2CNFSAT\) defined as follows: \(\left\{ \phi…
PYQ GATE 2014
Consider the decision problem defined as follows:
For example, is a Boolean formula and it is in .
The decision problem 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.
Attempted by 133 students.
Sign up free to check your answer
Sign up freeLoading lesson…

