Gate CS-2004 Question Paper With Solutions

Q. 86 The problems 3-SAT and 2-SAT are

(A) both in P

(B) both NP-complete

(C) NP-complete and in P respectively

(D) undecidable and NP-complete respectively

Answer: (C)

Explanation: