GATE CS 2004 Q30 — Asymptotic Worst Case Time and Space Complexity

The correct option is C.

Here is the classification of both problems:

• 3-SAT: This is a classic NP-complete problem. It is a special case of the Boolean satisfiability problem where each clause contains exactly three literals. It was one of Richard Karp's original 21 NP-complete problems.
• 2-SAT: This problem restricts each clause to have at most two literals. Unlike 3-SAT, 2-SAT can be solved in polynomial time, placing it in P.

Polynomial-time algorithm for 2-SAT:
A 2-SAT instance can be represented as an implication graph, where each clause $(u \lor v)$ is equivalent to two implications: $(\neg u \implies v)$ and $(\neg v \implies u)$. By constructing this directed graph and finding its Strongly Connected Components (SCCs) using Kosaraju's or Tarjan's algorithm, we can determine satisfiability in $O(V + E)$ linear time. If no variable $x$ and its negation $\neg x$ lie in the same SCC, the formula is satisfiable.

Thus, 3-SAT is NP-complete and 2-SAT is in P.