===========================================================================
CSC 363H              Tutorial Exercises for Week  8            Summer 2006
===========================================================================

 -  Show that RELPRIME = { <x,y> : x and y are relatively prime integers }
    belongs to P.

 -  Show that P and NP are both closed under union.

 -  Show that P is closed under complementation.

 -  Exercise 7.9 on p.295:
    A triangle in an undirected graph is a 3-clique. Show that TRIANGLE is
    in P, where TRIANGLE = { <G> : G contains a triangle }.