The GATE Grind

GATE 2014 CS (CS1) – Question 48

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

A polynomial-time algorithm correctly computing the largest clique of any graph is discovered. Which Venn diagram represents P, NP and NP Complete (NPC)?

Diagram for GATE 2014 CS (CS1) question 48
  1. Diagram A
  2. Diagram B
  3. Diagram C
  4. Diagram D

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Diagram D

Explanation

Such an algorithm solves the NP-complete clique decision problem in polynomial time, implying P=NP. The official diagram is **D**, also identifying NPC with those classes. Strictly, under standard many-one reductions, the trivial languages ∅ and Σ* remain in P=NP without being NP-complete; the key uses the usual informal omission of these degenerate exceptions.