Remember to explain your solutions clearly. A formula is not a complete solution, even if correct.

Exercise 1

Show that the following problems are in NP

(a) We call two graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. The problem is defined as follows. Iso = {(G, H) | G and H are isomorphic graphs.}

(b) A cut in a graph G = (V, E) is a separation of the vertices into two sets A and B such that A B = V. The size of a cut is the number of edges with one endpoint in A and one endpoint in B. The problem is defined as follows MaxCut = {(G, k) | G has a cut of size k or more.}

(c) Double-Sat = { | has at least two satisfying assignments}