[SOLVED] CS CS 535: Complexity Theory, Fall 2020 Homework 5

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|kv {0,1}c|x|kM(x,u,v) = 1.
(3 points)
(b) Prove that p2 = k=12TIME(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 Savitchs 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) = (xy1 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