%
% 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}
\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 3}
\smallskip
Due: 8:00PM, Friday, September 25, 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.
\begin{problem}[Hierarchy theorems and padding]
Recall the “padding argument” proof that complexity collapses such as $\P = \NP$ would scale up to $\EXP = \NEXP$. (Or equivalently, the complexity separation $\EXP \ne \NEXP$ would scale down to $\P \ne \NP$.)
\begin{enumerate}[(a)]
\item Show that if $\NTIME(n) \subseteq \TIME(n^2)$, then $\NTIME(n^2) \subseteq \TIME(n^4)$. % Show that if $\NTIME(n^{10}) \not\subseteq \TIME(n^{20})$, then $\NTIME(n^{2}) \notin \TIME(n^{4})$.
\begin{solution}
Your solution here.
\end{solution}
\item Show that for every $k \ge 1$, we have $\P \ne \NTIME(n^k)$.
Hint: Part (a) is not directly useful here, but the idea behind it is.
\begin{solution}
Your solution here.
\end{solution}
\end{enumerate}
\end{problem}
\medskip
\begin{problem}[$\NP$ vs. $\coNP$ relative to an oracle] The Baker-Gill-Solovay Theorem (Theorem 3.7 in Arora-Barak) shows that there is an oracle $A$ relative to which $\P^A \ne \NP^A$. This problem will walk you through a proof of the stronger result that $\NP^A \ne \coNP^A$ for some oracle. (The writeup is long, but the parts you have to fill in should be short!)
\begin{enumerate}[(a)]
\item A DNF formula $D$ is an $\OR$ of “terms,” where each term is an $\AND$ of literals. The \emph{width} of a DNF is the maximum number of literals appearing in any term and the \emph{size} is the number of terms.
For example, $(x_1 \land \overline{x_2}) \lor (x_2 \land x_3 \land x_4)$ is a DNF of width $3$ and size $2$.
Believe it or not, the whole proof rests on the following simple combinatorial fact\footnote{Well, in the same way that Baker-Gill-Solovay rests on the fact that $\OR_N$ cannot be computed by a “decision tree” of depth $