Models of Computation - Mathematics 450 - Fall 2006

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 the above hypothesis, can we know whether or not A can be solved in polynomial time without being given whether f is a polynomial or exponential function?
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.)
3.  
   1. Give an algorithm that adds two natural numbers x and y in polynomial time, where input size is defined as the number of digits in x written in base 10 plus the number of digits in y written in base 10.
   2. What would change in part a. above if we use base 2 instead of 10?
   3. Is the decision problem "x divides y" in P? If not, is it in NP? Support your answer. (Input size is the sum of the numbers of digits in x and in y.)
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. 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 can 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). Do URMs work like the first type of Turing Machines (i.e., in base 2) or the second type (tallying the 1's)?