Search code examples
algorithmcomputationp-np

Reduction of A to B : True or False

There are two statements: If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤ pB ), and B is NP-complete, then A must be NP-complete.

And:

If a decision problem B is polynomial-time reducible to a decision problem A (i.e., B≤ pA ), and B is NP-complete, then A must be NP-complete.

Which of the above statements are true?

Can you also give explanation?

Solution

  • the first statement is false because it means that by solving B and then applying some polynomial time algorithm you can solve A but maybe there is another way to solve A that doesn't require solving B and maybe it's only polynomial.

    the second statement is true because it means that you can solve B by first solving A then apply some polynomial time algorithm to solve B but B is NP-complete so A has to be NP-complete