These exercises are from Sipser, pages 271-274.

1. 7.5

2. 7.10

3. 7.11 (Two undirected graphs G and H are isomorphic is there is a bijection f that takes a vertex of G and produces a vertex of H, such that, for every pair of vertices (u,v) in G,

   (u,v) is an edge in G <=> (f(u),f(v)) is an edge in H

   A bijection is a function that is one-to-one and onto.)

4. 7.19. (Given a formula, try building another one that has twice as many satisfying assignments. How many more variables do you need for that? Think about it.)

5. 7.28 (You want to reduce, via a general reduction, the problem of factoring to some problem or problems in NP. You can use more than one problem if it helps. What decision problems would help you find a factor of a number efficiently?)