\documentstyle{article}
\input{preamble.tex}

\newcommand{\p}{{\rm P}}
\newcommand{\pspace}{{\rm PSPACE}}
\newcommand{\npspace}{{\rm NPSPACE}}
\newcommand{\np}{{\rm NP}}
\newcommand{\conp}{{\rm coNP}}
\newcommand{\exptime}{\hbox{EXPTIME}}
\newcommand{\ti}[1]{{\rm TIME}(#1)}
\newcommand{\spc}[1]{{\rm SPACE}(#1)}
\newcommand{\nspace}[1]{{\rm NSPACE}(#1)}
\newcommand{\conspace}[1]{{\rm coNSPACE}(#1)}
\newcommand{\aspace}[1]{{\rm ASPACE}(#1)}
\newcommand{\atime}[1]{{\rm ATIME}(#1)}
\newcommand{\ap}{{\rm AP}}
\newcommand{\al}{{\rm AL}}

\begin{document}
\lecture{7}{March 2, 1999}{Dan Spielman}{Eric Kuo} 

\section{The Baker-Gill-Solovay Theorem}
\begin{theorem}[Baker-Gill-Solovay]\label{BGS}
There exist oracles $A$ and $B$ for which $\p^A = \np^A$ and 
$\p^B \neq \np^B$.
\end{theorem}

{\it Proof:}
(A) Let $A=TQBF$.  Clearly, $\p^A \subseteq \np^A$ for any oracle $A$.
For the other direction, $\np^{TQBF} \subseteq
  \npspace^{TQBF} \subseteq \npspace$ 
since we can 
compute instances of $TQBF$ in polynomial space rather than asking the 
oracle. From Savitch's theorem, $\npspace \subseteq \pspace$.  And finally,
since $TQBF$ is PSPACE-complete, we have $\pspace \subseteq \p^{TQBF}$.
Hence $\p^{TQBF} = \np^{TQBF}$.

(B)  We need $L \in \np^B$, but $L \notin \p^B$.  We define $L_B$ as follows:
$$L_B = \{w| \exists x \in B : |x| = |w| \}$$
In other words, $L_B$ is the language of words which are the same length
of another word in $B$.  We see that $L_B \in \np^B$ because we can 
nondeterministically guess a word $x$ such that $|x|=|w|$ and then check
if it is in $B$.

We want to show that there is a $B$ for which $L_B \notin \p^B$.  We first
show how to construct an oracle to defeat one specific oracle TM $M^?$ 
(i.e. $L(M^?) \neq L_B$).
First, find some $n$ such that on input $0^n$, $M^?$ runs in fewer than
$2^n-1$ steps.  Simulate $M^?$ on input $0^n$, and answer ``no'' to all 
queries.  If $M^?$ ends up accepting $0^n$, simply let $B$ be the 
empty language.  That means $L_B$ is also empty, but the language of $M^?$
is not empty.  On the other hand, if $M^?$ rejects $0^n$, then let $x$
be the lexically least word of length $n$ for which $M^?$ did not query
the oracle.  Such a word must exist since $M^?$ ran in under $2^n-1$ steps.
So set $B = \{ x \}$.  That makes $0^n \in L_B$, so once again $L(M^?) \neq
L_B$.

Now we need to show that there is a $B$ such that for all polynomial time
oracle TMs $M^?$, $L(M^B) \neq L_B$.  First we let $M_1, M_2,$ etc. be an
enumeration of polynomial time oracle TMs.  We use the following algorithm:

\begin{enumerate}
\item First let $B_0 = \emptyset$.
\item For $i=1,2,3,\ldots$ do
\begin{enumerate}
\item Choose $n_i$ such that $\forall j<i$, $M_j^{B_{i-1}}$ does not
ask about any strings of length $n_i$ on input $0^{n_j}$.  In addition,
$M_i^{B_{i-1}}$ should run for at most $2^{n_i}-1$ steps on input $0^{n_i}$.
\item Simulate $M_i$ with oracle $B_{i-1}$ on input $0^{n_i}$.  (At this
point, $B_i$ has no strings of length $n_i$.)
\item If $M_i^{B_{i-1}}$ accepts, set $B_i = B_{i-1}$.  (So $M_i^{B_i}$
has accepted $0^{n_i}$, but $0^{n_i} \notin L_{B_i}$).
\item Else if $M_i^{B_{i-1}}$ rejects, then find $w$ such that $|w| = 
n_i$ and $M_i^{B_{i-1}}$ on input $0^{n_i}$ did not ask $w$.  Then set
$$B_i = B_{i-1} \cup \{ w \}.$$
(So we have $M_i^{B_{i-1}}$ rejecting $0^{n_i}$, but $0^{n_i} \in L_B$.)
\end{enumerate}
\item Set $B = \bigcup_{i=0}^{\infty}B_i$.  
\end{enumerate}

Note that $M_i^B$ is the same as $M_i^{B_i}$ for all $i$. $\Box$

\section{$\np^B \neq \conp^B$}
\begin{theorem}\label{PB!=coNPB}
There exists an oracle $B$ such that $\np^B \neq \conp^B$.
\end{theorem}

{\it Proof:\/} This proof is almost exactly like the previous one, except 
for a few highlighted modifications.

We need to show that there is a $B$ such that for all {\it coNP\/} 
oracle TMs $M^?$, $L(M^B) \neq L_B$.  First we let $M_1, M_2,$ etc. be an
enumeration of coNP  oracle TMs.  We use the following algorithm:

\begin{enumerate}
\item First let $B_0 = \emptyset$.
\item For $i=1,2,3,\ldots$ do
\begin{enumerate}
\item Choose $n_i$ such that $\forall j<i$, $M_j^{B_{i-1}}$ does not
ask about any strings of length $n_i$ on input $0^{n_j}$ {\it on any 
computation path.\/}  In addition,
$M_i^{B_{i-1}}$ should run for at most $2^{n_i}-1$ steps {\it on every
path of computation\/} on input $0^{n_i}$.
\item Simulate $M_i$ with oracle $B_{i-1}$ on input $0^{n_i}$.  (At this
point, $B_i$ has no strings of length $n_i$.)
\item If $M_i^{B_{i-1}}$ accepts, set $B_i = B_{i-1}$.  (So $M_i^{B_i}$
has accepted $0^{n_i}$, but $0^{n_i} \notin L_{B_i}$.
\item Else if $M_i^{B_{i-1}}$ rejects, then {\it choose some rejecting 
computation path,\/} and find $w$ such that $|w| = 
n_i$ and $M_i^{B_{i-1}}$ on input $0^{n_i}$ did not ask $w$ {\it on that
path.\/}  Then set
$$B_i = B_{i-1} \cup \{ w \}.$$
(So we have $M_i^{B_{i-1}}$ rejecting $0^{n_i}$ on that path, but $0^{n_i} \in L_B$.)
\end{enumerate}
\item Set $B = \bigcup_{i=0}^{\infty}B_i$.  
\end{enumerate}

Note that $M_i^B$ is the same as $M_i^{B_i}$ for all $i$. $\Box$

\section{Checking Polynomial Identities}
In this sectoin, we consider the problem of checking whether the sum of two 
products of polynomials is identical to the product of another set of 
polynomials.  Let $x_1, x_2, \ldots, x_n$ be variables, and $p_1, p_2,\ldots,
p_k, q_1, q_2, \ldots, q_k, r_1, r_2, \ldots, r_k$ be polynomials on
those variables.  The problem is to determine whether

$$\prod_{i=1}^k p_i(x_1, x_2, \ldots, x_n) 
+ \prod_{i=1}^k q_i(x_1, x_2, \ldots, x_n) 
- \prod_{i=1}^k r_i(x_1, x_2, \ldots, x_n) 
\equiv 0$$

To help us, we introduce Schwartz's Lemma.

\begin{lemma}[Schwartz's Lemma]\label{schwarz}
Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial of degree $d$.  Then
if $P \not \equiv 0$, then
$${\rm Pr}_{x_1, x_2, \ldots x_n \in S}[P(x_1, x_2, \ldots, x_n) = 0] 
\leq \frac{dn}{|S|}.$$
\end{lemma}

{\it Proof:\/}  We use induction on $n$.

{\it Base case\/}  $(n=1):$  If $P \not \equiv 0$, then there are at most
$d$ zeroes in $p$.  At most $d = d \cdot 1$ of them are in $S$.

{\it Inductive step:\/}  Write 
$$P(x_1, x_2, \ldots, x_n) = \sum_{i=0}^{d_1} x_1^i P_i(x_2, \ldots, x_n).$$
By hypothesis,
$${\rm Pr}_{x_2, \ldots, x_n} [P_{d_1}(x_2, \dots, x_n)=0] \leq 
\frac{(n-1)d}{|S|}.$$
If $P_{d_1}(x_2, \ldots, x_n) \neq 0$, then ${\rm Pr}_{x_1}[P(x_1, \ldots, x_n)]
\leq \frac{d_1}{|S|}$. $\Box$
\end{document}