Description

1.     Consider the Boolean formula φcell ∧ φstart ∧ φmove ∧ φaccept constructed in the proof of the Cook-Levin theorem. Let C = Q ∪ Γ ∪ {#} and α = the total number of all legal windows.

a.      Show in detail that φcell is in conjunctive normal form.

b.     Express the exact total number of clauses in φcell in terms of nk and |C|.

c.      Express the exact total number of literals in φcell in terms of nk and |C|.

d.     Express the exact total number of clauses in φmovecnf in terms of nk and α, where φmovecnf is the cnf-formula obtained from φmove by applying the conversion described in Fact 1.

e.      Express the exact total number of literals in φmovecnf in terms of nk and α.

f.       Express the exact total number of clauses in φcell ∧ φstart ∧ φmovecnf ∧ φaccept in terms of nk, |C|, and α.

g.     Express the exact total number of literals in φcell ∧ φstart ∧ φmovecnf ∧ φaccept in terms of nk, |C|, and α.

2.     Consider the conversion of cnf-formulas to 3-cnf-formulas described in Fact 2. In the case m > 3, prove rigorously that ℓ1 ∨ ··· ∨ ℓm is satisfiable iff (ℓ1 ∨ ℓ2 ∨ z1) ∧ (¬z1 ∨ ℓ3 ∨ z2) ∧ (¬z2 ∨ ℓ4 ∨ z3) ∧ ··· ∧ (¬zm−3 ∨ ℓm−1 ∨ ℓm) is satisfiable where the zi, 1 ≤ i ≤ m−3, are new variables.

3.     This question is about the duality of CLIQUE and VERTEX-COVER. For any undirected graph G = (V, E), the complement graph of G, denoted −G, is defined to be (V, −E) where −E = {(u, v) | u, v ∈ V, u ≠ v, (u, v) ∉ E }.

a.      Give an example graph G with seven vertices and show the complement graph −G.

b.     Prove that V' ⊆ V is a clique of G iff V−V' is a vertex cover of −G.

c.      In the graph G you gave in (a), choose a clique and show the corresponding vertex cover of −G.

d.     In the graph G you gave in (a), choose a vertex cover and show the corresponding clique of −G.

e.      Prove that CLIQUE ≤p VERTEX-COVER and VERTEX-COVER ≤p CLIQUE.

4.     Find a direct polynomial-time reduction for each of the following. Show that your reduction runs in polynomial time and prove the equivalence condition.

a.      VERTEX-COVER ≤p DOMINATING-SET

b.     DOMINATING-SET ≤p HUB-NODES-SELECTION

We showed in Assignment #2 that DOMINATING-SET and HUB-NODES-SELECTION are in NP.

5.     Consider the language U described in Problem 7.37 on page 327 (Problem 7.32 in the 2nd edition). We showed in Assignment #2 that U is in NP. Let L be any language in NP. Show that L ≤p U. Hint: Let M be a polynomial-time NTM that decides L.

6.     Study the reduction HAMPATH ≤p UHAMPATH in Theorem 7.55 on page 319 (page 291 in the 2nd edition) and solve Question 4 in the final exam review exercises. Also, find an example that shows that the reduction does not work if it only uses uin and uout without umid.