Models of Computation - Mathematics 352 - Fall 2009

For HW #20

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(m), where m denotes the input size of  an instance of A. Suppose also that B can be solved in polynomial time q(n), where n denotes the input size of  an instance of B. Finally, suppose that whenever we reduce A to B, an instance of A of size m reduces to an instance of B of size n = f(m). Then an instance of 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))
      5. q(f(p(m))
      6. f(p(m)) + q(n)
      7. f(p(m)) . q(n)
   2. Given that A can be reduced to B in polynomial time p(m), can we tell whether f is a polynomial function? 
   3. Prove that A can be solved in polynomial time.
2. How many digits are required to write a positive integer n in base b >1?Give your answer in terms of n and b. (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.)
3. 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 -- 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:
   Given n,
   1. Let k = 2.
   2. If k = n, output Yes (n is prime), and stop.
   3. If k divides n, output No (n is not prime), and stop.
   4. Let k = k+1.
   5. Go to 2.
   This algorithm runs in polynomial time, because:  
   It performs each of the 5 instructions at most n times. Of the 5 instructions, 4 of them count as only step each; one of the 5 instructions is a division, which takes a polynomial number of steps, say p(n). So, altogether, the algorithm performs at most n(4+p(n)) steps, which is a polynomial.