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