\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