Computer Science 4602, Fall 2019
Assignment 4

1. What is the definiton of class P?

2. Suppose that L is a set of natural numbers, and suppose that there is an algorithm that takes a natural number n and tells you whether n ∈ L in time O(n²). Can you conclude that L is in P based on that? Explain.

3. Suppose that L is a set of strings, and suppose that there is an algorithm that takes a string x and tells you whether x ∈ L in time O(2ⁿ), where n = |x|. Can you conclude that L is not in P based on that? Explain.

4. Is P closed under union? Justify your answer.

5. A triangle in a simple graph consists of three mutually adjacent vertices. Show that the problem of determining whether a simple graph contains a triangle is in P.

6. Let DOUBLE-SAT be the problem about propositional formulas φ in 3-CNF form: {φ | φ has at least two different satisfying truth-value assignments}. Prove that DOUBLE-SAT is in NP.

7. A k-coloring of a simple graph G is a way of assigning one of k colors to each vertex of G so that no two adjacent vertices have the same color. Show that the problem COLOR = {(G, k) | G has a k-coloring} is in NP.

8. A bijection is a function that is one-to-one and onto (a one-to-one correspondence).

   An isomorphism between two simple graphs G = (V_G, E_G) and H = (V_H, E_H) is a bijection f  from V_G to V_H such that, for every pair of different vertices x and y in V_G,

   (x, y) ∈ E_G ⇔ (f (x), f (y)) ∈ E_H.

   That is, an isomorphism preserves edges and nonedges: If (x, y) is an edge in G then (f (x), f (y)) is an edge in H, and if (x, y) is not an edge in G, then (f (x), f (y)) is not an edge in H.

   Two simple graphs are isomorphic if there is an isomorphism from one to the other.

   Let ISO = {(G, H) | G and H are isomorphic simple graphs}. Prove that ISO is in NP.