Reference no: EM132294083

1) Show that P is closed under union, concatenation, and complement.

2) Let CONNECTED = {?G?| G is a connected undirected graph}. Analyze the algorithm given on page 185 to show that this language is in P.

3) A triangle in an undirected graph is a 3-clique. Show that TRIANGLE ∈ P, where TRIANGLE = {?G?| G contains a triangle}.

4) Let MODEXP = {?a, b, c, p?| a, b, c, and p are positive binary integers such that ab ≡ c (mod p)}.

Show that MODEXP ∈ P. (Note that the most obvious algorithm doesn't run in polynomial time. Hint: Try it first where b is a power of 2.)

5) Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions.

a. 1274 and 10505

b. 7289 and 8029