CS 334: Problem Set 6

CS 334: Problem Set 6.
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.)
b. (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.
i. (5 points) Give a high-level description of your algorithm, with sufficient detail.
ii. (2 points) What is the maximum number of queries made by your algorithm?
iii. (3 points) Explain why your algorithm correctly finds a satisfying assignment for a satisfiable
formula.