Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
A)P is NP-complete
B)P is NP-hard but not NP-complete
C)P is in NP but not NP-complete
D)P is neither NP-hard nor in NP

Question

Quizplus · Accepted Answer

To prove a problem P is NP-complete, two conditions must be satisfied: (1) P is in NP, and (2) every problem in NP is reducible to P in polynomial time. X's reduction from 3-SAT to P shows P is at least as hard as 3-SAT (a known NP-complete problem), satisfying the second condition for NP-completeness. Y's reduction from P to 3-SAT suggests P can be solved in polynomial time if 3-SAT can, implying P is in NP. Together, these reductions satisfy both conditions for NP-completeness.

Two Persons X and Y Have Been Asked to Show