Decide True or False for each of the followings You MUST bri

Decide True or False for each of the followings. You MUST briefly justify your answer. If P = NP, then all problems in NP can be solved in polynomial time deterministically. It is known that Satisfiability is NP-complete. Assume that an O(n^2016) deterministic algorithm has been found for the Satisfiability problem, then P = NP. If a decision problem A is NP-complete, proving that A is reducible to B, in polynomial time, is sufficient to show that B is NP-complete.

Solution

a) If P = NP, afterward all problems in NP can be solved in polynomial time deterministically.

True, because p is solved in polynomial time so that if P = NP all the NP can be solved in polynomial time.

b) Assume that an O(n^2016) deterministic algorithm has been found for the 3-SAT problem, then P = NP.

True, if one NP Complete problem is solve in polynomial time than all other can be solved in polynomial time.

c) If a decision problem A is NP-complete, proving that A is reducible to B, in polynomial time, is sufficient to show that B is NP-complete.

False, if A NP complete problem is reduced in other problem , it will be NP hard. so here B is NP hard but it is not guarantee that B is NP