Reduction arrows are easy to reverse under exam pressure, especially when NP membership and NP-hardness appear together. Class membership, NP-hardness, NP-completeness, SAT and reduction direction become easier once the arrow is read as: a solver for the target also solves the source. Attempt each before reading its answer, and write every reduction with its source on the left. For the wider subject route, see GATE CS Exam Preparation.
1. P and NP foundations: Questions 1-3
Q1. (GATE 2015; solved question)
Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?
(a) Only II
(b) Only III
(c) Only I and II
(d) Only I and III
Correct answer: (d) Only I and III.
A decider halts on every input, so swapping accept and reject makes the complement Turing decidable. Every NP language has a nondeterministic polynomial-time decider and is decidable. Thus I and III are true; II is false.
Q2. (GATE 2013; solved question)
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in an undirected graph is in NP. 3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
(a) 1, 2 and 3
(b) 1 and 2 only
(c) 2 and 3 only
(d) 1 and 3 only
Correct answer: (a) 1, 2 and 3.
DFS or BFS detects a cycle in (O(V+E)), proving statement 1. Since (P \subseteq NP), statement 2 follows. NP-complete problems have nondeterministic polynomial-time algorithms, proving statement 3.
Q3. (GATE 2012; solved question)
Assuming P ≠ NP, which of the following is TRUE?
(a) NP-complete = NP
(b) NP-complete ∩ P = \(\phi\)
(c) NP-hard = NP
(d) P = NP-complete
Correct answer: (b) NP-complete ∩ P = \(\phi\).
If an NP-complete problem had a polynomial-time algorithm, every NP problem could reduce to it and enter P. With (P \subseteq NP), that would give (P=NP), contradicting the assumption.
2. co-NP and NP-completeness boundaries: Questions 4-5
Q4. (UGC NET 2019; solved question)
Consider the complexity class \(CO-NP\) as the set of languages \(L\) such that \(\overline{L} \in NP\), and the following two statements: \(S_1: P \subseteq CO-NP\) \(S_2: \text{ If } NP \neq CO-NP, \text{ then } P \neq NP\) Which of the following is/are correct?
(a) Only \(S_1\)
(b) Only \(S_2\)
(c) Both \(S_1\) and \(S_2\)
(d) Neither \(S_1\) nor \(S_2\)
Correct answer: (c) Both \(S_1\) and \(S_2\).
P is closed under complement, so (S_1) follows: (L \in P \Rightarrow \overline L \in P \subseteq NP \Rightarrow L \in co\text{-}NP). For (S_2), the contrapositive of (P=NP \Rightarrow NP=co\text{-}NP) is (NP \ne co\text{-}NP \Rightarrow P \ne NP).
Q5. (GATE 2006; solved question)
A problem in NP is NP-complete if
(a) It can be reduced to the 3-SAT problem in polynomial time
(b) The 3-SAT problem can be reduced to it in polynomial time
(c) It can be reduced to any other problem in NP in polynomial time
(d) Some problem in NP can be reduced to it in polynomial time
Correct answer: (b) The 3-SAT problem can be reduced to it in polynomial time.
The stem gives NP membership. Since 3-SAT is NP-complete, (3\text{-SAT} \le_p X) proves X is NP-hard. The reverse arrow, (X \le_p 3\text{-SAT}), does not.
Claim to prove | What the reduction must show | What is still missing |
|---|---|---|
In NP | Candidate reduces to a known NP problem | NP-hardness |
NP-hard | Known NP-complete source reduces to candidate | Membership in NP |
NP-complete | Both directions above are established | Nothing |
3. Polynomial-time reduction direction: Questions 6-8
Q6. (GATE 2015; solved question)
Consider two decision problems \(Q_1,Q_2\) such that \(Q_1\) reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to \(Q_2\). Then which one of the following is consistent with the above statement?
(a) \(Q_1\) is in NP, \(Q_2\) is NP hard.
(b) \(Q_2\) is in NP, \(Q_1\) is NP hard.
(c) Both \(Q_1\) and \(Q_2\) are in NP.
(d) Both \(Q_1\) and \(Q_2\) are NP hard.
Correct answer: (a) \(Q_1\) is in NP, \(Q_2\) is NP hard.
From (Q_1 \le_p 3\text{-SAT} \le_p Q_2), the first arrow places (Q_1) in NP; the second makes (Q_2) NP-hard. Neither (Q_2 \in NP) nor (Q_1) NP-hard follows.
Q7. (GATE 2015; solved question)
Language \(L_1\) is polynomial time reducible to language \(L_2\). Language \(L_3\) is polynomial time reducible to \(L_2\), which in turn is polynomial time reducible to language \(L_4\). Which of the following is/are true? I. if \(L_4 \in P\), then \(L_2 \in P\) II. if \(L_1 \in P\) or \(L_3 \in P\), then \(L_2 \in P\) III. \(L_1 \in P\), if and only if \(L_3 \in P\) IV. if \(L_4 \in P\), then \(L_1 \in P\) and \(L_3 \in P\)
(a) II only
(b) III only
(c) I and IV only
(d) I only
Correct answer: (c) I and IV only.
Trace (L_1 \le_p L_2 \le_p L_4) and (L_3 \le_p L_2 \le_p L_4). If (L_4 \in P), composition gives \(\{L_1,L_2,L_3,L_4\} \subseteq P\), proving I and IV. An easy source says nothing about its target, so II and III do not follow.
Q8. (GATE 2006; solved question)
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
(a) R is NP-complete
(b) R is NP-hard
(c) Q is NP-complete
(d) Q is NP-hard
Correct answer: (b) R is NP-hard.
For every (A \in NP), (A \le_p S \le_p R), so R is NP-hard. Its NP membership is unknown, and (Q \le_p S) does not make Q hard.
4. SAT and clique reductions: Questions 9-12
Q9. (UGC NET 2014; solved question)
We can show that the clique problem is NP-hard by proving that
(a) CLIQUE ≤ P 3-CNF_SAT
(b) CLIQUE ≤ P VERTEX_COVER
(c) CLIQUE ≤ P SUBSET_SUM
(d) None of the above
Correct answer: (d) None of the above.
Hardness needs a known hard source reducing to CLIQUE; every option points outward. For (F=(x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3 \vee x_4) \wedge (x_2 \vee \neg x_3 \vee \neg x_4)), create nine literal-occurrence vertices, joining compatible literals from different clauses. The vertices for (x_2) in clause 1, (x_3) in clause 2 and (x_2) in clause 3 form a size-3 clique. This illustrates (3\text{-SAT} \le_p CLIQUE), opposite every listed arrow.
Q10. (GATE 2003; solved question)
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
(a) Π is NP-hard but not NP-complete
(b) Π is in NP, but is not NP-complete
(c) Π is NP-complete
(d) Π is neither NP-hard, nor in NP
Correct answer: (c) Π is NP-complete.
Ram's (3\text{-SAT} \le_p \Pi) proves NP-hardness. Shyam's \(\Pi \le_p 3\text{-SAT}\), with (3\text{-SAT} \in NP), proves \(\Pi \in NP\). Together they prove NP-completeness.
Q11. (GATE 2014; solved question)
Consider the decision problem \(2CNFSAT\) defined as follows: \(\left\{ \phi \mid \phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\right\}\) For example, \(\phi = (x1 \vee x2) \wedge (x1 \vee \bar{x3}) \wedge (x2 \vee x4)\) is a Boolean formula and it is in \(2CNFSAT\). The decision problem \(2CNFSAT\) is
(a) NP-Complete.
(b) solvable in polynomial time by reduction to directed graph reachability.
(c) solvable in constant time since any input instance is satisfiable.
(d) NP-hard, but not NP-complete.
Correct answer: (b) solvable in polynomial time by reduction to directed graph reachability.
The clauses give six edges: \(\neg x_1 \to x_2\), \(\neg x_2 \to x_1\), \(\neg x_1 \to \neg x_3\), \(x_3 \to x_1\), \(\neg x_2 \to x_4\), and \(\neg x_4 \to x_2\). The formula is satisfiable iff no variable and its negation share a strongly connected component. SCC computation takes (O(V+E)), so 2-CNF-SAT is in P.
Q12. (GATE 2004; solved question)
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
Correct answer: (c) NP-complete and in P respectively.
3-SAT is NP-complete; 2-SAT uses Q11's polynomial-time implication-graph SCC algorithm. Clause width two therefore changes the complexity classification.
5. P, NP and reducibility answer-pattern recap
Pattern | Safe inference |
|---|---|
\(A \le_p B, B \in P\) | \(A \in P\) |
\(A \le_p B, A\) NP-hard | B is NP-hard |
Known NP-complete \(S \le_p X\) | X is NP-hard |
\(X \le_p S, S \in NP\) | \(X \in NP\) |
Answer key
1-d, 2-a
3-b, 4-c
5-b, 6-a
7-c, 8-b
9-d, 10-c
11-b, 12-c
6. How P, NP and reducibility are tested in these PYQs
Questions 1-4 test whether class inclusions and complement closure support a conclusion. Questions 5-10 test the direction of a polynomial reduction: an NP-hard source reducing to X proves X is NP-hard, while X reducing to a problem in NP proves X is in NP. Questions 11-12 test the boundary between 2-SAT in P and NP-complete 3-SAT, including the implication-graph SCC test for 2-SAT.
7. P, NP and reducibility: the short version and next step
A target solver also solves the source. An NP-hard source reducing to X proves X hard; NP-completeness also needs NP membership. Continue with GATE Guidance by Sanchit Sir, or take a timed GATE Test Series. Redraw Q6-Q7's arrows and Q11's six edges, then retry all 12.
