\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<n_2<\cdots$, such that
\begin{enumerate}
\item
$M_i^{B_i}(0^{n_i})\neq(0^{n_i}\in L(B_i))$.
\item
$M_i^{B_i}(0^{n_i})=M_i^B(0^{n_i})$.
\item $0^{n_i}\in
L(B_i)\Leftrightarrow0^{n_i}\in L(B)$.
\end{enumerate}

The construction
algorithm is as follows:

\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 fewer than $2^{n_i}$ 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$.) This will answer no to all 
queries
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}$).\\
If
$M_i^{B_{i-1}}$ rejects, then find $x$ such that $|x| = 
n_i$ and
$M_i^{B_{i-1}}$ on input $0^{n_i}$ did not ask $x$.  Then set
$$B_i =
B_{i-1} \cup \{ x \}.$$
(So we have $M_i^{B_{i-1}}$ rejecting $0^{n_i}$,
but $0^{n_i} \in L(B)$, just as in the warm-up.)
\end{enumerate}
\end{enumerate}
Set $B = \bigcup_{i=0}^{\infty}B_i$.  \end{proof}

One can
similarly prove that there exists an oracle $B$ such that $\np^B \neq
\conp^B$.


\section{Randomized
Computation}
\begin{definition}[RP]
$L\in\rp$ (randomized polynomial time)
if $\exists$ a randomized (can ``toss coins" along the way) 
polynomial
time TM $M$ s.t. $\forall x: 
\begin{array}{ll}x\in L \Rightarrow \pr[M(x)
{\rm\ accepts}]\geq{2\over3}\\
x\not\in L \Rightarrow \pr[M(x) {\rm\
accepts}]=0\end{array}$.
\end{definition}

For example, it is easy to show
that Composites $\in\rp$ via elementary number theory (Euler's 
theorem).
It is also true, but nontrivial, that Primes $\in\rp$. Clearly
$\rp\subseteq\np$
(existentially guess every random
choice).

\begin{definition}[BPP]
$L\in\bpp$ (bounded (error) probabilistic
polynomial time) if $\exists$ a randomized 
poly time TM $M$ and a
polynomial $p(\cdot)$ s.t. $\forall x: 
\begin{array}{ll}x\in L \Rightarrow
\pr_{r\in\{0,1\}^{p(|x|)}}[M(r,x) {\rm\ accepts}]\geq{2\over3}\\
x\not\in L
\Rightarrow \pr_{r\in\{0,1\}^{p(|x|)}}[M(r,x) {\rm\
accepts}]\leq{1\over3}\end{array}$.
\end{definition}

The choice of
${2\over3}$ and ${1\over3}$ is somewhat arbitrary. See the amplification
lemma in the 
next lecture. In the proof of the following proposition, we
will show that the bounds can be 
replaced by $1-2^{-n-1}$ and
$2^{-n-1}$.

\begin{proposition} $\rp\subseteq\bpp\subseteq\p/{\rm
poly}$.\end{proposition}

\begin{proof}
The first containment is obvious.
For the second, the idea is to use values of $r$ 
as advice strings. Turn
error into $2^{-n-1}$ for strings of length $n$.

Say we have $M$ s.t.
$\forall_{|x|=n}\pr_{r\in\{0,1\}^{p(|x|)}}[M(r,x) {\rm\ is\
wrong}]<2^{-n-1}$. 
There are $2^n$ $x$ of length $n$, therefore

$\pr_r[\exists x:|x|=n {\rm\ and\ } M(r,x) {\rm\ is\
wrong}]<2^n\cdot2^{-n-1}={1\over2}<1 
\Rightarrow \exists r$ s.t. $\forall
|x|=n$, 
$x\in L\Leftrightarrow M(r,x)$ accepts (see probability
handout).
Build this $r$ in as the advice string.

The only detail left is
that we can get the error down to $2^{-n-1}$. For this, we run the machine

$kn$ times ($k$ to be specified later), and accept if it accepts a
majority of the time. The 
probability of getting the wrong answer is the
probability of being wrong at least half of the 
time, or

$$\sum_{i=0}^{kn/2}{kn\choose
i}\left({2\over3}\right)^i\left({1\over3}\right)^{kn-i}=
\left({1\over3}\right)^
{kn}\sum_{i=0}^{kn/2}{kn\choose i}2^i.$$
Since the sum over all $i$ of
${kn\choose i}$ is $2^{kn}$, and each $2^i$ term is at most $2^{kn/2}$, 
we
can easily bound this probability from above by
$\left({1\over3}\right)^{kn}2^{kn}2^{kn/2}=
\left({2\sqrt2\over3}\right)^{kn}$.
Since $2\sqrt2<3$, we can find $k$ large enough so that this 
probability
is less than $2^{-n-1}$, as desired. \end{proof}

\end{document}