Imagine that you have a problem P that you know is N P-complete. For this problem you have two algorithms to solve it. For each algorithm, some problem instances of P run in polynomial time and others...

Imagine that you have a problem P that you know is N P-complete. For this problem you have two algorithms to solve it. For each algorithm, some problem instances of P run in polynomial time and others run in exponential time (there are lots of heuristic-based algorithms for real N P-complete problems with this behavior). You can’t tell beforehand for any given problem instance whether it will run in polynomial or exponential time on either algorithm. However, you do know that for every problem instance, at least one of the two algorithms will solve it in polynomial time.

(a) What should you do?

(b) What is the running time of your solution?

(c) What does it say about the question of P = N P if the conditions described in this problem existed?