Question

Suppose there are two problems, C and P.

C is known to be NP-Complete

Suppose that I want to prove that P is also NP-Complete

Which of the following is the correct method to do this?

Question 3 options:

1)	Show that problem P is in NP, then show how to comvert problem P into problem C in polynomial time.

2)	Show that problem P is in NP, then show how to comvert problem C into problem P in polynomial time.

Answer 1

Right option is option (2)

As C is already known to be NP-complete and also polynomial time reducible to P, as asserted in option (2), P has to be NP-complete,otherwise if P is not NP-complete, then by reversing the calculations we can reach from P to C, and in that case C also would not be NP-complete, which is a contradiction about C's NP-completeness.

If we go by the first option then we see, a polynomial-time reduced instance C of P may be NP_complete although P need not be so.