CS 535: Complexity Theory, Fall 2020 Homework 8
Due: 2:00AM, Saturday, November 14, 2020.
Reminder. Homework must be typeset with LATEX preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions by yourself without assistance. You must also identify your collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problem 0 (Term Paper). Give the paper you are reviewing a careful reading and start thinking about the structure and content of your review. (A draft of your review is due on Nov. 21, so don’t delay!)
Problem 1 (NP, BPP, and RP).
(a) Suppose NP ⊆ BPP. Show that SearchSAT can be solved in randomized polynomial- time. That is, show that there is a probabilistic poly-time algorithm M such that for all satisfiable CNF formulas φ, we have that M(φ) outputs a satisfying assignment to φ with probability at least 2/3. (7 points)
(b) Use part (a) to conclude that if NP ⊆ BPP, then NP = RP. (5 points)
Problem 2 (Counting Cycles). A Hamiltonian cycle in a directed graph G is a cycle that visits every vertex in G exactly once. Define the problem #HAM1 as follows: Given a directed graph G, count the number of Hamiltonian cycles in G. It is known that #HAM is #P-complete. Use this fact to prove that #CYCLE is also #P-complete. (8 points)
1I’m not so sure about sharp ham, but I like my ham with sharp cheddar. 1