CS 535: Complexity Theory, Fall 2020 Homework 4
Due: 8:00PM, Friday, October 9, 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 1 (“Mid”-Semester Feedback Form). Please fill out the feedback form here: https: //forms.gle/YdQ2tqHsfbM6VcxH9. (It’s anonymous, so we can’t check whether you did it, but we value your voice!)
Problem 2 (Time vs. Space). As usual, you can quote anything stated in the main body of Arora-Barak or during the lectures to solve these problems. (Which may give some of them very short solutions.)
(a) Show that NL ⊆ P. (2 points)
(b) Define PolyL = ∪∞c=1SPACE(logc n). Show that NL ⊆ PolyL. (2 points)
(c) Prove that there are no PolyL-complete problems (with respect to logspace reductions). Hint: Assume that such a complete problem were to exist. Show that it would contradict the space hierarchy theorem. (4 points)
(d) DefinetheclassSC(“Steve’sClass,”inhonorofStephenCook)toconsistofalllanguages A for which there exists a deterministic TM M deciding A that runs in time poly(n) and uses space poly log(n). It is an open question whether NL ⊆ SC. Explain why parts (a) and (b) together do not resolve this open question. (2 points)
Problem 3 (Consequences of NL = coNL).
(a) Let S(n) ≥ logn be a space-constructible function. Show that NSPACE(S(n)) =
coNSPACE(S(n)). (4 points)
(b) Define the language DLEN to consist of all tuples ⟨G, s, t, d⟩ where G is an directed graph, and the distance from s to t in G is exactly d. (That is, there exists a path from s to t of length d and there is no shorter path.) Prove that DLEN is NL-complete. (6 points)
1
Problem 4 (*Bonus Problem* Implication SAT). An “implication CNF” is a CNF where every clause has at most one positive variable. For example, (x1 ∨ x2 ∨ x3) ∧ (x4 ∨ x1 ∨ x2) is an implication CNF, but (x1 ∨ x2 ∨ x3) ∧ (x4 ∨ x1 ∨ x2) is not. The name comes from the (useful) fact that the logical expression x1 ∨x2 ∨···∨xk is equivalent to (x2 ∧···∧xk) → x1.
(a) Define the language IMPSAT = {φ | φ is a satisfiable implication CNF}. Prove that IMPSAT is P-complete under logspace reductions.
(b) What goes wrong in your proof if you use it to try to show that IMPSAT is NP-complete?
Hint: You can make the same kinds of simplifying assumptions that we made in our proof sketch of the Cook-Levin Theorem from class—single-tape TM, binary tape alphabet, input padded with trailing zeroes. Focus more on the main ideas than on the details.
2