CS 535: Complexity Theory, Fall 2020 Homework 5
Due: 8:00PM, Friday, October 16, 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 (Alternation).
(a) Let k ∈ N. Prove that a language L ∈ Σ2TIME(nk) if and only if there exists a constant
c and a (deterministic) TM M(x,u,v) running in O(|x|k) steps such that x ∈ L ⇐⇒ ∃u ∈ {0,1}c|x|k∀v ∈ {0,1}c|x|kM(x,u,v) = 1.
(3 points)
(b) Prove that Σp2 = ∪∞k=1Σ2TIME(nk). (2 points)
(c) Let s(n) ≥ n be space constructible. Prove that NSPACE(s(n)) ⊆ ATIME((s(n))2). Hint: Recall the proof of Savitch’s Theorem. (6 points)
Problem 2 (Polynomial Hierarchy).
(a) Define the language
∃USAT = {φ a Boolean formula | ∃x ∈ {0,1}n ∃!y ∈ {0,1}mφ(x1,…,xn,y1,…,ym)}.
Here, the notation “∃!” means “there exists exactly one” (satisfying y). For example, φ(x,y1,y2) = (x∧y1 ∧y2)∨(x ̄∧y1) ∈ ∃USAT because setting x = 1 makes y1 = 1 and y2 = 0 the unique satisfying assignment to the formula. Show that ∃USAT is Σp2- complete. (6 points)
(b) Suppose that one day, science shows that Σp6 ⊆ Πp4 . Show that the polynomial hierarchy collapses, to the lowest level that you can. (3 points)
Problem 3 (* Bonus * Our Pal AL). Let AL = ASPACE(log n) be the class of languages decidable in logarithmic space by an alternating TM. Prove that P = AL.
1