\documentstyle{article}
\input{preamble.tex}
\newcommand{\p}{{\rm
P}}
\newcommand{\rp}{{\rm RP}}
\newcommand{\bpp}{{\rm
BPP}}
\newcommand{\pr}{{\rm Pr}}
\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{6}{February 27,
2001}{Dan Spielman}{Edward Early}
\section{Relativization, The
Baker-Gill-Solovay
Theorem}
\begin{theorem}[Baker-Gill-Solovay]\label{BGS}
$\exists$ oracles
$A$ and $B$ for which $\p^A = \np^A$ and
$\p^B \neq
\np^B$.
\end{theorem}
Before giving a proof, we discuss relativization,
i.e. stuff with oracles. We can relativize the proof in the previous
lecture to get $\np^A \subseteq \p^A/\mathrm{poly} \Rightarrow
(\Sigma_2^\p)^A=(\Pi_2^\p)^A$. Of the four ATIME, ASPACE containment
theorems that we proved earlier, three of them relativize.
Note that, in
light of the Baker-Gill-Solovay theorem, any technique that relativizes
won't resolve P vs. NP. In general, if we want to compare complexity
classes $C_1$ and $C_2$, it can be helpful to ask if there exists $A$ such
that $C_1^A=C_2^A$, or if equality holds for most $A$. For example, Sipser
proved that $\exists A$ s.t. $\forall k (\Sigma_k^P)^A\neq(\Pi_k^P)^A$,
adding to the plausibility that the polynomial hierarchy does not
collapse.
While it is known that IP=PSPACE, it was previously known that
$\exists A$ s.t.
IP$^A\neq$PSPACE$^A$ (moreover, the proof of equality
appeared to relativize, prompting lots of debate). Hence the quantum result
$\exists A$ s.t. BQP$^A\neq\np^A$ is nothing to get too excited
about.
\bigskip
\begin{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) The idea is that nondeterminism gives us more powerful
access to the
oracle, allowing us to ask more questions than a
deterministic TM can.
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$, i.e.
for every PTIME OTM $M^?$, $\exists x$ s.t. $M^B(x)$
rejects but
$x\in L(B)$ or $M^B(x)$ accepts but $x\not\in L(B)$. Our proof
will be by
diagonalization.
As a warm-up, we first
show how to construct
an oracle to defeat one specific OTM $M^?$
(i.e. $L(M^?) \neq L(B)$). Let
$p(n)$ be a polynomial upper bound on the
running time of $M^?$ on input
$0^n$. Then we can find $n$ such that on
input $0^n$, $M^?$ runs in fewer
than
$2^n$ steps. Simulate $M^?$ on input $0^n$, and answer ``no'' to all
queries (i.e. take $?=\emptyset$). 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^?$ contains $0^n$.\\
On the other hand, if $M^?$
rejects $0^n$, then let $x$
be a word of length $n$ for which $M^?$ did not
query
the oracle. Such a word must exist since $M^?$ ran in $p(n)<2^n$
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
OTMs $M^?$, $L(M^B) \neq L(B)$. First we let $M_1,
M_2,$ etc. be an
enumeration of polynomial time oracle TMs. We construct a
sequence
$B_0\subseteq B_1\subseteq\cdots\subseteq B$, with lengths
$n_1