Description
Problem 1. (10 points) A triangle in an undirected graph is a cycle of length 3. Show that the language = {〈 〉: ℎ } is in .
Problem 2. (10 points) Language is polynomial-time reducible to , denoted < , if there is a polynomial-time computable function such that
∈ ⇔ ( ) ∈ .
a. (5 points) Show that if ∀ , ∈ , if ≠ and ≠ Σ∗ then < . (Hint: this is easier than it seems since ∈ . Now use the definition.)
-
(5 points) Show that if =then every language, other than and Σ∗, in is
-Complete.
Problem 3. (10 points) Behold, a genie appears before you! Given a formula ( 1, 2, … , ) in conjunctive normal form with boolean variables, the genie will correctly tell you (in one step) whether or not the formula is satisfiable. Unfortunately, the genie will not give you a truth assignment to the variables that makes the formula true.
Your problem is to figure out a satisfying truth assignment when the genie says the formula is satisfiable.
You can present the genie with a polynomial (in ) number of queries.
-
(5 points) Give a high-level description of your algorithm, with sufficient detail.
-
(2 points) What is the maximum number of queries made by your algorithm?
-
(3 points) Explain why your algorithm correctly finds a satisfying assignment for a satisfiable formula.
