Polynomial time reducibility

Given two problems, A and B, suppose each instance I_A of A can be reduced to an instance I_B of B in polynomial time p(m), where m denotes the size of I_A and p is a polynomial function. Suppose also that each instance I_B of B can be solved in polynomial time q(n), where n denotes the size of I_B and q is a polynomial function. Finally, suppose each instance I_A of size m reduces to an instance I_B of size n = f(m).

1. An instance I_A of size m can be solved in which of the following times? Explain why.

   1. p(m) + q(f(m))

   2. p(m) + f(q(m))

   3. p(m) . f(q(m))

   4. p(m) . q(f(m))

2. Prove f = O(g) for some polynomial function g. (Hint: use the fact that A can be reduced to B in polynomial time.)

3. Prove that A can be solved in polynomial time.

In class, we showed that the Graph Coloring problem can be reduced to the Diophantine Equation problem. Prove that this reduction can be done in polynomial time.

How many digits are required to write a positive integer n in base b >1? Give your answer in terms of n and b; you may use floor, ceiling, logarithm, and other common functions. Prove your answer. (Suggestion: if you don't know where to start, try a few different n's with b = 10 and b = 2 to see what's going on. If you don't remember how "bases" work, there are lots of elementary expositions on the web.)