%
% 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 6}

\smallskip

Due: 8:00PM, Friday, October 23, 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.

\bigskip

\setcounter{problem}{-1}
\begin{problem}[Term Paper] Now would be a good time to start thinking about the term paper assignment: what topic/paper you might be interested in writing about, and who you might want to work with. Instructions for the term paper are here: \url{https://cs-people.bu.edu/mbun/courses/535_F20/handouts/term_paper.pdf} and a list of suggested topics is here: \url{https://piazza.com/class/keda2wyieyz10e?cid=277}.
\end{problem}

\medskip

\begin{problem}[Exponential-Size Circuits for Every Function]
	In this problem, you will prove that every Boolean function $f: \zo^n \to \zo$ can be computed by a circuit of size $O(2^n / n)$. As we'll see, this is essentially tight: in fact, ``most'' functions require circuits of size $\Omega(2^n / n)$.
	\begin{enumerate}[(a)]
		\item First show that every Boolean function $f(x_1, \dots, x_n)$ can be written in the form $(\overline{x_n} \land f_0(x_1, \dots, x_{n-1})) \lor (x_n \land f_1(x_1, \dots, x_{n-1}))$ for some functions $f_0, f_1 : \zo^{n-1} \to \zo$. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Use part (a) recursively to show that every function $f : \zo^k \to \zo$ is computed by a circuit of size $O(2^k)$. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item There are exactly $2^{2^k}$ different functions $f : \zo^k \to \zo$. Combine this fact with part (b) and another recursive application of part (a) to show that every function $f: \zo^n \to \zo$ for $n \ge k$ can be computed a circuit of size $O(2^{n-k}) + O(2^k \cdot 2^{2^k})$. Hint: You can assume each gate has unbounded fan-out, so you can ``reuse'' the output of a subcircuit as many times as you want. (4 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Set $k$ appropriately in part (c) to conclude that every Boolean function $f : \zo^n \to \zo$ is computed by a circuit of size $O(2^n / n)$. (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 see how far you can push the technique to get different tradeoffs. Assume every function you encounter is time- and space-constructible.
	 \begin{enumerate}[(a)]
	 	\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{TISP}(T, S) \subseteq \class{\Sigma_2TIME}(\sqrt{T S})$. (3 points)
	 	
%		Uncomment this before adding your solution...LaTeX issues...
%	 	\begin{solution}
%	 		Your solution here.
%	 	\end{solution}
 	
	 	\item Generalize Claim 5.11.2 in Arora-Barak to prove that if $\NTIME(n) \subseteq \TIME(n^c)$ for some $c > 1$, then $\class{\Sigma_2TIME}(f(n)) \subseteq \NTIME((f(n))^c)$. (3 points)
	 	
%		Uncomment this before adding your solution...LaTeX issues...
%	 	\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) to prove that for every $c < \sqrt{2}$, there exists a $\delta > 0$ such that $\NTIME(n) \not\subseteq \class{TISP}(n^{c}, n^{\delta})$. You don't have to show it, but this implies that $\SAT$ cannot be solved by an algorithm using $O(n^{1.41\dots})$ time and $n^{o(1)}$ space. Hint: Note that $\delta$ is allowed to depend on $c$. You'll want to choose $\delta$ small enough so that $c(c+ \delta) < 2$. (2 points)

%		Uncomment this before adding your solution...LaTeX issues...
%	 	\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 $\NTIME(n) \not\subseteq \class{TISP}(n^{1+\delta}, n^c)$.  This result implies that $\SAT$ cannot be solved by an 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)
	 	
%		Uncomment this before adding your solution...LaTeX issues...
%	 	\begin{solution}
%	 		Your solution here.
%	 	\end{solution}
 	
	 \end{enumerate}
\end{problem}

\bigskip

\begin{problem}[*Bonus* Improved Time-Space Tradeoffs] Now let's see how we can get even better tradeoffs by repeatedly trading alternations for time. Note that by combining Problems 2(a) and (b), we get the statement: If $\NTIME(n) \subseteq \TIME(n^c)$ for some $c > 1$, then $\class{TISP}(T, S) \subseteq \NTIME((TS)^{c/2})$.
	\begin{enumerate}[(a)]
	\item Suppose $\NTIME(n) \subseteq \TIME(n^c)$ for some $c > 1$.  Use the above statement to show that $\class{TISP}(T, S) \subseteq \class{coNTIME}((TS^2)^{c^2 / (2+c)})$. 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 Conclude that $\NTIME(n) \not\subseteq \class{TISP}(n^c, n^{o(1)})$ whenever $c^3 < 2 + c$, i.e., $c < 1.521\dots$.
	\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}






