The problems 3-SAT and 2-SAT are
2004
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
Attempted by 13 students.
Show answer & explanation
Correct answer: C
3-SAT is NP-complete, meaning it cannot be solved in polynomial time unless P=NP. 2-SAT, on the other hand, is solvable in polynomial time using algorithms such as finding strongly connected components in implication graphs. Therefore, 3-SAT is NP-complete and 2-SAT is in P.