%
% 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.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

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

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi


\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators 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}

\ifnum\inclsolns=1
	\makeatletter
	\noindent 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 Savitch's 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}






