===========================================================================
CSC 363H                        Exercise 5                        Fall 2007
===========================================================================

A.  Show that UNARY-PRIMES = { 1^n : n is prime } belongs to P.

B.  Show that TRIANGLE = { <G> : G is an undirected graph that contains a
    triangle } belongs to P, where a "triangle" in a graph is a set of
    three vertices with all edges between them present in the graph.

C.  Show that P is closed under complementation, i.e., for all languages
    L in P, ~L in P.

D.  Prove or disprove:  A_TM in NP.