1. Show that the set P of languages decidable in polynomial time is closed under union, intersection and coplementation. In other words, if languages A and B are in P, the A union B, A intersect B, and A-bar are in P

2. Show that the set of languages NP is closed under union

3. Sipser 7.8

4. Sipser 7.10

5. A graph is called bipartite if there exists is an assignment of colors {blue, red} to each vertex such that no edge adjoins two nodes of the same color. No node may have more than one color associated with it. Show that the set of encodings of bipartite graphs is in P

6. Sipser 7.12