GATE CS 2014 Set 3 Q.48 (CS Q.38): Asymptotic Analysis and Time/Space Complexity

Consider the decision problem 2CNFSAT defined as follows:

\{\Phi \mid \Phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\}

For example, $\Phi = (x_1 \lor x_2) \land (x_1 \lor \overline{x_3}) \land (x_2 \lor x_4)$ is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

NP-Complete.

solvable in polynomial time by reduction to directed graph reachability.

solvable in constant time since any input instance is satisfiable.

NP-hard, but not NP-complete.

Official answer and solution

Solution

Recall the complexity and algorithmic reduction of the 2-Satisfiability (2-SAT) problem.

2-CNF Satisfiability (2-SAT):
In a 2-CNF formula, each clause has at most two literals (e.g., $u \lor v$ ).
Every such clause is logically equivalent to two implications:
$(u \lor v) \equiv (\neg u \to v) \equiv (\neg v \to u).$
Reduction to Implication Graph:
- Construct a directed graph $G = (V, E)$ where vertices represent all literals ( $x_i$ and $\neg x_i$ ), and directed edges represent the implication rules.
- A formula is satisfiable if and only if no variable $x_i$ and its negation $\neg x_i$ lie in the same Strongly Connected Component (SCC) of $G$ .
Complexity:
- Finding SCCs in a directed graph takes linear time $O(V + E)$ using Tarjan's or Kosaraju's algorithm.
- Reachability between literals can be checked in polynomial (linear) time.
- Thus, 2CNFSAT is solvable in polynomial time by reduction to directed graph reachability (option B).
Other options are incorrect: 3-SAT is NP-complete, but 2-SAT is in P (not NP-complete).

Final answer

Common trap

Confusing 2-SAT (in P) with 3-SAT (NP-complete).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.