Computer Science 4602, Fall 2016
Assignment 6

Exercises are from Sipser, third edition, beginning on page page 239 for Chapter 5 and on page 322 for Chapter 7.

1. 5.4
2. 5.23
3. 5.30(b,c)
4. 5.31

5. Here is a definition of a function that decides whether an integer x ≥ 2 is prime.

     prime(x)
      for i = 2,...,x-1 do
        if i is a factor of x
          return false
        end if
      end for
      return true
   

   1. Is that a polynomial-time algorithm to determine if an integer x > 2 is prime?

   2. Can you conclude that the set of prime numbers is in P based solely on that algorithm?

   3. Can you conclude that the set of prime numbers is not in P based solely on that algorithm?

6. Is P closed under union? Justify your answer.

7. 7.9