%
% 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{enumitem}
\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 2023}

\bigskip

{\Large Homework 4}

\smallskip

Due: 11:59PM, Tuesday, October 3, 2023.

\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

\begin{problem}[Padding and Time Hierarchies] Hint: Use part (a) to solve part (b).
	\begin{enumerate}[label=(\alph*)]
		\item Show that if $f, g, t$ are time-constructible, and $\TIME(f(n)) = \TIME(g(n))$, then $\TIME(f(t(n))) = \TIME(g(t(n)))$. (4 points)
		\item Show that $\TIME(n) \ne \TIME(n \log n)$. (4 points)
	\end{enumerate}
\end{problem}

\begin{problem}[$\NP$ vs. $\PSPACE$ 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 that there is also an oracle $A$ relative to which $\NP^A \ne \PSPACE^A$. This proof will hopefully illuminate a general recipe for proving oracle separations.
	\begin{enumerate}[label=(\alph*)]
		\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 $<N$.}: The function $\XOR_N(x_1, \dots, x_N) = x_1 \oplus \dots \oplus x_N$ cannot be computed by a DNF $D(x_1, \dots, x_N)$ of width $< N$. Prove this fact. (4 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item Another way to think of an oracle $A$ is as an infinitely long vector, indexed by binary strings. That is, for $z \in \zo^*$, let $A_z = 1$ if $z \in A$ and $A_z = 0$ if $z \notin A$. Recall that to query $A$, a TM can write a string $z$ to its oracle tape and receive the bit $A_z$.
		
		For an oracle $A$, define the unary language
		\begin{align*}
			L_\XOR(A) &= \{1^n \mid \XOR_{2^n}((A_z)_{z \in \zo^n})\} \\
			&=\{1^n \mid z \in A \text{ for an odd number of strings } z \in \zo^n\}.
		\end{align*}
		Show that $L_\XOR(A) \in \PSPACE^A$ for every oracle $A$. (4 points)
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Now our job is construct an oracle $A$ for which $L_\XOR(A) \notin \NP^A$. We'll do this by first arguing that the output of an $\NP^A$ machine is just a DNF applied to the oracle $A$.
		
		Let $M$ be a nondeterministic oracle Turing machine running in time $T(n)$. Show that for every $n \in \N$ there exists a DNF formula $D_n$ of width at most $T(n)$ and size at most $2^{O(T(n))}$ such that for every oracle $A$,
		\[M^A(1^n) = 1 \iff D_n(A) = 1,\]
		again regarding $A$ as an infinite vector $(A_z)_{z \in \zo^*}$. (4 points)
		
		Hint 1: When run on an input of length $n$, the machine $M$ can query the oracle at most $T(n)$ times.
		
		Hint 2: A binary tree of depth $T$ has at most $2^T$ leaves.
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}

	Your job is done now, but stick around for the exciting conclusion! Next we diagonalize against all nondeterministic machines running in time $T(n) = 2^n/10$ to instantiate the oracle $A$. Let $M_1, M_2, \dots$ be an enumeration of such machines, with each machine appearing infinitely often in the list. We construct an oracle $A^*$ such that for every machine $M_i$ in the enumeration, there exists an input $1^{n_i}$ such that $M^{A^*}_i(1^{n_i}) = 1 \iff 1^{n_i} \notin L_{\XOR}(A^*)$.
	
	We construct $A^*$ iteratively as follows. We initialize $A^*$ to be the empty language, and in each round $i$, commit to including or excluding strings of a certain length $n_i$ in $A^*$. We choose $n_i$ large enough so that no string of length $n_i$ has had its fate decided in any previous round. 
	
	Let $D_{n_i}$ be the DNF formula guaranteed by part (c) capturing the behavior of machine $M_i$ on input $1^{n_i}$. By part (a), there exists an oracle $A^{(i)}$ such that
	\[D_{n_i}(A^{(i)}) \ne \XOR_{2^{n_i}}((A^{(i)}_z)_{z \in \zo^{n_i}}).\]
	Actually, something stronger is true. Since $\XOR_{2^{n_i}}(A)$ only depends on the values of $A_z$ for $z \in \zo^{n_i}$, we may assume that $A^{(i)}_z = A^*_z$ for every $|z| < n_i$.
	
	Now for all of the (finitely many) $z$ for which the variable $A_z$ appears in the DNF $D_{n_i}$, set $A^*_z = A^{(i)}_z$. That is, for each such $z$, commit to including $z$ in $A^*$ if $z \in A^{(i)}$ and commit to excluding $z$ from $A^*$ if $z \notin A^{(i)}$. Then by part (b),
	\[M_i^{A^*}(1^{n_i}) = 1 \iff D_{n_i}(A^*) = 1 \iff \XOR_{2^{n_i}}((A^*_z)_{z \in \zo^{n_i}}) = 0 \iff 1^{n_i} \notin L_{\XOR}(A^*).\]
	
	
	Let $M$ be any nondeterministic TM running in time $T_M(n) = \poly(n)$. Let $n_*$ be sufficiently large so that $T_M(n^*) \le 2^{n^*} / 10$. Since $M$ appears infinitely often in our enumeration, there exists some $n \ge n_*$ such that $M^{A^*}(1^n) = 1 \iff 1^n \notin L_\XOR(A^*)$. Hence, $L_\XOR(A^*)$ is not decided by any poly-time NTM, so $L_\XOR(A^*) \notin \NP^{A^*}$.
	
	On the other hand, we showed in part (b) that $L_\XOR(A) \in \PSPACE^A$ for every oracle $A$, and in particular for $A^*$. Hence $\NP^{A^*} \ne \PSPACE^{A*}$.
\end{problem}

\newpage

	\begin{problem}[*Bonus Problem*, $\NP$ vs. $\PSPACE$ relative to a random oracle] Are oracles that separate $\NP$ from $\PSPACE$ rare, or are they common? In this problem, you'll show that $\NP^A \ne \PSPACE^A$ not only for some contrived oracle $A$, but for \emph{almost all} oracles.
	\begin{enumerate}[label=(\alph*)]
		\item Show that for sufficiently large $N$, for every DNF $D$ of width at most $\sqrt{N}$, 
		\[\Pr_{x \sim \zo^N}[D(x) \neq \XOR_N(x)] \ge 0.1.\]
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Let $A \subseteq \zo^*$ be a random oracle. That is, for every string $z \in \zo^*$, include $z$ in $A$ independently with probability $1/2$. Show that $\NP^A \ne \PSPACE^A$ with probability at least $0.99$ over the choice of the random oracle $A$.\footnote{Complexity class separations satisfy a \emph{zero-one law}, which implies that the probability of a separation is actually $1$.}
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\end{document}






