Question

1. Suppose that problem A polynomial-time reduces to problem B, in other words, we can
find a polynomial time algorithm that uses solutions to instances of problem B (given
by an oracle - aka “fairy godmother”) to solve problem A.
1a. If problem A can be shown to be NP-complete, what does that tell us about
problem B?
1b. If problem B can be shown to be in P, what does that tell us about problem A?

Answer 1

1 (a) . If problem A is NP time complexity and problem A give solutions to instances of problem B . Then problem B will also have NP time complexity as it will class problem A again and again so it can't have Polynomial time.

1 (b). If Problem B is shown in P , then problem A will also be in P time complexity as B uses A for it's solution.