Gate 2003 Questions on Theory of Computation

One mark Questions:

1. Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAP Problem to Π, and shyam shows a polynomial time deduction from Π to 3-SAP which of the following can be inferred from these reduction ?

(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.

Answer: c

Explanation:

Ram shows 3-SAT ≤_p Π
Shyam shows Π ≤_p 3-SAT

Step-I: Now if p₁ ≤_p p₂ and if p₁ is np-complete, we can say that p₂ is np-hard. Now Ram has shown 3-SAT ≤_p Π and we know that 3-SAT is an np-complete problem. Therefore, we can conclude that Π  np-hard.

Step-II: If p₁ ≤_p p₂ and if p₂ belongs to np than p₁ also must belongs to np.
But shyam has shown that Π ≤_p 3-SAT, and we know that 3-SAT is np-complete and hence it belongs to np.
So Π also must belongs to np.

In step-I we showed that Π is np-hard.
In step-II we showed that Π belongs to np.

So is Π np-complete.