%
% 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{enumitem}
\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 2023}

\bigskip

{\Large Homework 5}

\smallskip

Due: 11:59PM, Tuesday, October 17, 2023.

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

\bigskip

\begin{problem}[Logspace Computability] Let $f : \zo^* \to \zo^*$. Prove that the following two statements are equivalent:
	\begin{enumerate}
		\item The function $f$ is logspace computable in the sense that we defined in class. That is, there is a TM with a read-only input tape and write-only/write-once output tape that computes $f$ using only $O(\log n)$ cells of its (non-input, non-output) work tapes.
		\item The function $f$ is implicitly logspace computable in the sense of Arora-Barak. That is, $f$ is polynomially-bounded (i.e., there exists a polynomial $p$ such that $|f(x)| \le p(|x|)$ for every $x$) and the languages $\{\langle x, i\rangle \mid i \le |f(x)|\}$ and $\{\langle x, i \rangle \mid (f(x))_i =1\}$ are both in $\L$.
	\end{enumerate}
	(4 points)
\end{problem}

\begin{problem}[$\NL$-Completeness] \hfill
		\item Recall that a directed graph is a DAG (directed acyclic graph) if it does not contain a directed cycle. Show that the language
		\[\mathprob{DAGPATH} = \{\langle G, s, t\rangle \mid G \text{ is a DAG and has a path from } s \text{ to } t \}\]
		is $\NL$-complete. (7 points)
\end{problem}

\begin{problem}[Boolean and Polynomial Hierarchies] \hfill
	\begin{enumerate}[label=(\alph*)]
		\item Define the Boolean hierarchy inductively as follows:
		\begin{align*}
			\class{BH}_1 &= \NP \\
			\class{BH}_{2i} &= \{A \cap B \mid A \in \class{BH}_{2i-1}, B \in \coNP\} \\
			\class{BH}_{2i+1} &= \{A \cup B \mid A \in \class{BH}_{2i}, B \in \NP\} \\
			\class{BH} &= \bigcup_{i = 1}^\infty \class{BH}_i.
		\end{align*}
		That is, the Boolean hierarchy consists of languages that can be written as a finite combination of unions, intersections, and complements of languages in $\NP$. Show that $\class{BH} \subseteq \P^{\NP} \subseteq \Sigmacc{2} \cap \Picc{2}$. (3 points)
		\item \textbf{*Individual Review* (No collaboration allowed for this part only)} \\ Define the language $\mathprob{SATTAUT} = \{\langle \varphi, \psi \rangle \mid \varphi \in \SAT, \psi \in \mathprob{TAUT}\}$. Show that $\mathprob{SATTAUT}$ is $\class{BH}_2$-complete under poly-time (Karp) reductions. (4 points)
		\item 	Show that if the polynomial hierarchy does not collapse, then $\P \subsetneq \class{PH} \subsetneq \PSPACE$. (2 points)
		
		Hint: There's a one-sentence solution to this given what's shown in Arora-Barak and in class.
		\item \textbf{(Bonus)} Show that if the Boolean hierarchy collapses, then the polynomial hierarchy collapses.
	\end{enumerate}
\end{problem}


\end{document}






