[SOLVED] CS decision tree %

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

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

smallskip

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

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
e NEXP$ would scale down to $P
e NP$.)
begin{enumerate}[(a)]
itemShow that if $NTIME(n) subseteq TIME(n^2)$, then $NTIME(n^2) subseteq TIME(n^4)$. % Show that if $NTIME(n^{10})
otsubseteq TIME(n^{20})$, then $NTIME(n^{2})
otin TIME(n^{4})$.
begin{solution}
Your solution here.
end{solution}
item Show that for every $k ge 1$, we have $P
e 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
e NP^A$. This problem will walk you through a proof of the stronger result that $NP^A
e 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 factfootnote{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 $