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.) Given two problems, A and B, suppose A can be reduced to B in polynomial time p(n), where n denotes the input size for Problem A. Suppose further that B can be solved in polynomial time p_B(n). Then can 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 implicitly assumed that after the reduction from A to B, the input size for B is still n. How would the above change if after the reduction the 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 2^n?
2. Prove that any positive integer n, when written in base b >1, has floor(log_b(n)) + 1 digits, where floor(x) denotes the greatest integer less than or equal to x.. (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.)
3.  
   1. Prove that adding two numbers x and y can be done in polynomial time, where input size is defined as the number of digits in x (when written in base 10) plus the number of digits in y (when written in base 10).
   2. What would change in part a. above if we use base 2 instead of 10?
   3. Prove that checking whether x divides y can be done in polynomial time, where input size is defined as in part a. Hint: review the long-division algorithm you learned in elementary school!
4. Find and explain what is wrong with the following "proof" that the problem "n is prime" is in P. (After several centuries, it was finally proved very recently -- in 2002 -- that "n is prime" is indeed in P [PRIMES is in P], [PDF].  But the "proof" below is certainly not it.)
   Consider the following algorithm:
   1. Given n. Let k = 2.
   2. If k divides n, output No (n is not prime), and stop.
   3. k++.
   4. If k = n, output Yes (n is prime), and stop.
   5. Go to 2.
   This algorithm runs in polynomial time, because: (i) it checks at most n times whether or not k divides n, (ii) checking if k divides n takes only polynomial time, by problem III above, and (iii) n times any polynomial is still a polynomial.
5. [Optional -- think about this problem and be prepared to discuss it in class] In a Turing Machine that only uses symbols 0 and 1, we can make the convention that natural numbers are written in base 2; or, we could make the convention that a number n is represented by writing n 1's on the tape. Discuss how these two different conventions would affect the study of Complexity for certain problems (e.g., problem III above). What about URMs?