edited by
8,012 views
15 votes
15 votes

Ram and Shyam have been asked to show that a certain problem $\Pi$ is $\text{NP-complete}.$ Ram shows a polynomial time reduction from the $\text{3-SAT}$ problem to $\Pi$, and Shyam shows a polynomial time reduction from $\Pi$ to $\text{3-SAT.}$ Which of the following can be inferred from these reductions?

  1. $\Pi$ is NP-hard but not NP-complete

  2. $\Pi$ is in NP, but is not NP-complete

  3. $\Pi$ is NP-complete

  4. $\Pi$ is neither NP-hard, nor in NP

edited by

3 Answers

Best answer
13 votes
13 votes
C. For a problem to be NP-Complete, it must be NP-hard and it must also be in NP.

Ram's reduction shows that $\Pi$ is NP hard because it must be at least as hard as $3$-SAT which is a known NP-Complete problem. Here, $\Pi$ need not be NP-Complete.

Now, Shyam's reduction shows that $3$-SAT problem is at least as hard as $\Pi$ or equivalently $\Pi$ is not harder than $3$-SAT. Since $3$-SAT is in NP, $\Pi$ must also be in NP.

Thus, $\Pi$ is NP-hard and also in NP $\implies$ $\Pi$ is NP-Complete.
edited by
0 votes
0 votes
ans is A as  second condition doesn't imply that II is in NP same way as NP problem reduced to NP hard doesn't imply that  problem is NP hard
0 votes
0 votes

π is NP-C. 

Answer:

Related questions

15 votes
15 votes
7 answers
3
Kathleen asked Sep 18, 2014
11,658 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...
9 votes
9 votes
3 answers
4
Kathleen asked Sep 12, 2014
7,300 views
Which of the following problems is not $\text{NP}$-hard?Hamiltonian circuit problemThe $0/1$ Knapsack problemFinding bi-connected components of a graphThe graph coloring ...