%
% 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.
%
definclsolns{0}
documentclass[12pt]{article}
usepackage{fullpage}
usepackage{graphicx}
usepackage{enumerate}
usepackage{comment}
usepackage{amsmath,amssymb,amsthm}
usepackage{hyperref}
input{macros}
theoremstyle{definition}
ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi
makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators 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}
ifnuminclsolns=1
makeatletter
oindent 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)
otsubseteq 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)
otsubseteq 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.41dots})$ 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}itemNow 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)
otsubseteq 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}bigskipbegin{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’
e 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)
otsubseteq class{TISP}(n^c, n^{o(1)})$ whenever $c^3 < 2 + c$, i.e., $c < 1.521dots$.begin{solution}Your solution here.end{solution}item Generalize the above argument inductively to show that $NTIME(n)
ot subseteq class{TISP}(n^c, n^{o(1)})$ whenever $c(c-1) < 1$, i.e., $c < phi = 1.618dots$.begin{solution}Your solution here.end{solution}end{enumerate}end{problem}end{document}
Reviews
There are no reviews yet.