%
% 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}
\usepackage{tikzsymbols, halloweenmath}

\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 $\Cat$ Homework 6 $\pumpkin$}

\smallskip

Due: 11:59PM, Tuesday, October 31, 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.


\setcounter{problem}{-1}
\begin{problem}[Term Paper Topic] Your term paper topic and partner (if applicable) are due on
	Gradescope at the same time this homework assignment is. Instructions for the term paper are here: \url{https://cs-people.bu.edu/mbun/courses/535_F23/handouts/term_paper.pdf} and a list of suggested topics is here: \url{https://piazza.com/class/lm5tyuo0a7j2fu/post/89}.
\end{problem}

\begin{problem}[$\NC^1$ Captures Poly-Size Boolean Formulas]
	For this problem, all circuits have fan-in $2$ $\{\land, \lor\}$ gates, and you can assume all negations are pushed to the bottom. A Boolean formula is a special case of a circuit where every intermediate $\land$ or $\lor$ gate has fan-out $1$. To make the accounting in this problem easier, we'll write ``$C$ has $s$ gates'' to mean that $C$ has $s$ $\{\land, \lor\}$ gates, explicitly \underline{not} including the $2n$ inputs and their negations. 
	\begin{enumerate}[label=(\alph*)]
		\item Suppose $f : \zo^n \to \zo$ is computed by a \underline{circuit} with $s$ gates and depth $d$. Show that $f$ is also computed by a \underline{formula} of size $O(2^d \cdot s)$. (2 points)
		
		Hint: Induction on the depth.
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Now we'll get to work on the converse, showing how to convert a formula into a low-depth circuit. First, prove the following fact about binary trees: For every binary tree with $s$ vertices, there exists a vertex $v$ such that the subtree rooted at $v$ contains between $s/3$ and $2s/3$ vertices. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Use part (b) to show that every formula $F$ with $s$ gates has an equivalent formula $F' = (A \land B) \lor (C \land D)$, where each subformula $A, B, C, D$ has at most $2s/3$ gates. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Use part (c) recursively to show that every formula with $s$ gates has an equivalent formula of depth $O(\log s)$ and $\poly(s)$ gates. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Combine parts (a) and (d) to conclude that a language is in the complexity class $\NC^1$ if and only if it is also computable by a poly-size family of formulas. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\bigskip

\begin{problem}[More Time-Space Tradeoffs] In class (and in Arora-Barak) we saw that $\NTIME(n) \not\subseteq \class{TISP}(n^{1.2}, n^{0.2})$, and hence $\SAT$ cannot be solved by a deterministic TM running in, say, time $O(n^{1.1})$ and space $O(n^{0.1})$ simultaneously. In this problem, you'll similarly prove that co-nondeterministic linear time cannot be simulated in small \emph{nondeterministic} time and space, and how far you can push the technique to get different tradeoffs. Assume every function you encounter in this problem is time- and space-constructible.
	
For time bound $T(n)$ and space bound $S(n)$, define $\class{NTISP}(T, S)$ to be the class consisting of languages $L$ such that $L$ is decidable by a \underline{nondeterministic} TM running in both time $O(T(n))$ and space $O(S(n))$. Define $\class{coNTIME}(T(n)) = \class{\Pi}_1\class{TIME}(T(n))$ to be the class of languages decidable by a alternating TM of $\class{\Pi}_1$ type in time $O(T(n))$.
	\begin{enumerate}[label=(\alph*)]
		\item Generalize Claim 5.11.1 in Arora-Barak to prove that for $T(n) \ge n^2$ and $S(n) \ge \log n$, we have $\class{NTISP}(T, S) \subseteq \class{\Sigma}_2\class{TIME}(\sqrt{T S})$. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item Generalize Claim 5.11.2 in Arora-Barak to prove that if $\class{co}\NTIME(n) \subseteq \NTIME(n^c)$ for some $c > 1$, then $\class{\Sigma}_2\class{TIME}(f(n)) \subseteq \NTIME((f(n))^c)$. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item 
		First we'll see how large we can make the time requirement. Use parts (a) and (b), together with the following Fact (which you can assume without proof), to prove that for every $c < \sqrt{2}$, there exists a $\delta > 0$ such that $\class{coNTIME}(n) \not\subseteq \class{NTISP}(n^{c}, n^{\delta})$. (2 points)
		\begin{fact} \label{fact:hierarchy}
			For all positive constants $b > a > 0$, we have
			\[\class{coNTIME}(n^b) \not\subseteq \NTIME(n^a).\]
		\end{fact}
		
		 Hint: Note that $\delta$ is allowed to depend on $c$. You'll want to choose $\delta$ small enough so that $c(c+ \delta) < 2$.
		 
		 You don't have to show it, but this implies that $\mathprob{TAUT}$ cannot be solved by a nondeterministic TM using $O(n^{1.41\dots})$ time and $n^{o(1)}$ space. 

		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item 
		Now we'll see how far we can push the space requirement. Prove that for every $c < 1$, there exists a $\delta > 0$ such that $\class{coNTIME}(n) \not\subseteq \class{NTISP}(n^{1+\delta}, n^c)$.  This result implies that $\mathprob{TAUT}$ cannot be solved by a nondeterministic algorithm using $n^{1+o(1)}$ time and  $O(n^{0.999})$ space. Hint: This time, choose $\delta$ small enough so that $(c + 1 + \delta)(1+\delta) < 2$. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item (*Bonus*) Prove Fact~\ref{fact:hierarchy}.
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
	\end{enumerate}
\end{problem}

\newpage

\begin{problem}[*Bonus* Improved Deterministic Time-Space Tradeoffs] Let's go back to the setting of deterministic time-space tradeoffs for $\NTIME(n)$. In this problem, you'll see how to get even better tradeoffs by repeatedly trading alternations for time.
	\begin{enumerate}[label=(\alph*)]
		\item Suppose $\NTIME(n) \subseteq \TIME(n^c)$ for some $c > 1$.  Show that $\class{TISP}(T, S) \subseteq \class{coNTIME}((TS^2)^{c^2 / (2+c)})$. Use this to conclude that $\NTIME(n) \not\subseteq \class{TISP}(n^c, n^{o(1)})$ whenever $c^3 < 2 + c$, i.e., $c < 1.521\dots$. Hint: Let $C_0, C_f$ be the start and accept configurations of a deterministic TM running in time $T$. Then $C_f$ is reachable from $C_0$ in $T$ time steps iff \emph{for all} $C' \ne C_f$, we have that $C'$ is \emph{not} reachable from $C_0$ in $T$ time steps.
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Generalize the above argument inductively to show that $\NTIME(n) \not \subseteq \class{TISP}(n^c, n^{o(1)})$ whenever $c(c-1) < 1$, i.e., $c < \phi = 1.618\dots$.
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}


\end{document}






