[SOLVED] CS %

%
% To use this as a template for turning in your solutions, change the flag
% inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the author and collaborators fields as
% appropriate. Write your solutions where indicated.
%

definclsolns{0}
documentclass[12pt]{article}

usepackage{fullpage}
usepackage{graphicx}
usepackage{enumerate}
usepackage{comment}
usepackage{amsmath,amssymb,amsthm}
usepackage{hyperref}

input{macros}

theoremstyle{definition}

ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi

makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators given}}
makeatother

author{Ada Lovelace}
collaborators{Charlie Babbage, Mike Faraday}

begin{document}

begin{center}
{Large CS 535: Complexity Theory, Fall 2020}

bigskip

{Large Homework 5}

smallskip

Due: 8:00PM, Friday, October 16, 2020.

end{center}

ifnuminclsolns=1
makeatletter
oindent Name: @author \
Collaborators: @collaborators
makeatother
else
fi

paragraph{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 {em 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.

medskip

begin{problem}[Alternation] hfill
begin{enumerate}[(a)]
item Let $k in N$. Prove that a language $L in class{Sigma_2TIME}(n^k)$ 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 in L iff exists u in zo^{c|x|^k} forall v in zo^{c|x|^k} M(x, u, v) = 1.] (3 points)
item Prove that $Sigmacc{2} = cup_{k =1}^{infty}class{Sigma_2TIME}(n^k)$. (2 points)
item Let $s(n) ge n$ be space constructible. Prove that $NSPACE(s(n)) subseteq class{ATIME}((s(n))^2)$. Hint: Recall the proof of Savitchs Theorem. (6 points)
end{enumerate}
end{problem}

medskip

begin{problem}[Polynomial Hierarchy] hfill
begin{enumerate}[(a)]
item Define the language
[mathprob{exists USAT} = {varphi text{ a Boolean formula}mid exists x in zo^n exists! y in zo^m varphi(x_1, dots, x_n, y_1, dots, y_m)}.]
Here, the notation $exists!$ means there exists exactly one (satisfying $y$). For example, $varphi(x, y_1, y_2) = (x land y_1 land overline{y_2}) lor (bar{x} land y_1) in mathprob{exists USAT}$ because setting $x = 1$ makes $y_1 = 1$ and $y_2 = 0$ the unique satisfying assignment to the formula. Show that $mathprob{exists USAT}$ is $Sigmacc{2}$-complete. (6 points)
item Suppose that one day, science shows that $Sigmacc{6} subseteq Picc{4}$. Show that the polynomial hierarchy collapses, to the lowest level that you can. (3 points)
end{enumerate}
end{problem}

medskip
begin{problem}[* Bonus * Our Pal $class{AL}$]
Let $class{AL} = class{ASPACE}(log n)$ be the class of languages decidable in logarithmic space by an alternating TM. Prove that $P = class{AL}$.
end{problem}

end{document}