Models of Computation - Mathematics 450 - Spring 2005

For HW #25

Problems marked [Optional] should be done, but turn them in only if you're not sure how to do them.

1.  
   1. (See pages 171-172 of Wilf.) Suppose Problem A is reduced to Problem B in polynomial time p(n), when n denotes input size, and p is a polynomial. Suppose further that Problem B can be solved in polynomial time p_B(n). Then can Problem A be solved in time p(n) + p_B(n) or in time p(n) . p_B(n)? Explain why.
   2. In the above, we assumed that after the reduction from A to B, the input size for B is still n. How would the above change if input size for B was instead q(n), where q is a polynomial? What if instead of being a polynomial, q(n) = 2^n? Could q(n) possibly be be 2^n?