Reference no: EM132298056
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