Gate CS-2014-3 Question Paper With Solutions

Q. 48 Consider the decision problem 2CNFSAT defined as follows:
Gate CS-2014-3 Question Paper With Solutions(A) NP-Complete

(B) solvable in polynomial time by reduction to directed graph reach-ability

(C) solvable in constant time since any input instance is satisfiable

(D) NP-hard, but not NP-complete

Answer: (B)

Explanation:

Gate CS-2014-3 Question Paper With Solutions

Learn More:   Gate EE-2012 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here