\documentstyle[12pt,amstex,psfig]{article}

\input{preamble.tex}

\begin{document}
\lecture{7}{February 27, 1997}{Daniel A. Spielman}{Mark Skandera}

\section{Probabilistic Complexity Classes}

Imagine that a turing machine can flip coins to decide
whether or not a string $x$ is in language $L$.
Naturally, we want the machine to decide correctly most of the
time, perhaps with probability at least 2/3.
To describe the different conceptual behaviors of such algorithms,
we define several probabilistic complexity classes.
Surprisingly, we may define these classes with or without 
explicitly using probability.

\begin{definition}
$BPP$ is the class of all languages $L$ for which there is a 
nondeterministic polynomial time TM, $M$, whose computation
branches all have the same length, and which has the following
properties.

If $x \in L$ then at least 2/3 of the branches accept.

If $x \not\in L$ then at most 1/3 of the branches accept.
\end {definition}

\noindent
Alternatively, using probability, we could say that

\vspace{5mm}
When $x \in L$ then $Pr[ M(x)$ accepts $] \geq 2/3$

When $x \notin L$ then $Pr[ M(x)$ accepts $] < 1/3$

\vspace{5mm}
\noindent
Note that by both definitions, $M$ is guaranteed to halt in polynomial
time, with all branches halting together.

For the many probabilistic algorithms which have only a one-sided
error, we define another class.

\begin{definition}
$RP$ is the class of all languages $L$ for which there is a
nondeterministic polynomial time TM, $M$, whose computation
branches all have the same length, and which has the following
properties.

When $x \in L$ then $Pr[ M(x)$ accepts $] \geq 2/3$

When $x \notin L$ then $Pr[ M(x)$ accepts $] = 0$

\end{definition}

Actually, most languages in $BPP$ are known to be in $RP$ or $Co-RP$.
For example, COMPOSITES is in both $RP$ and $Co-RP$.
The intersection of $RP$ and $Co-RP$ is an interesting class also,
and has its own name.

\begin{definition}
$ZPP$ is the class $RP \cap Co-RP$.
\end{definition}

The numbers 1/3 and 2/3 in the above definitions may seem somewhat
arbitrary, and in fact they are.  We can reduce the error probability 
of an algorithm almost as much as we like by simple repitition.  
Note that after $k$ 
(independent) repetitions of an $RP$ algorithm, (assuming that we
accept if any single repetition accepts)

\vspace{5mm}
If $x \not\in L$, then $M(x)$ rejects on every repetition.

If $x \in L$, then $M(x)$ rejects with probability at most $(1/3)^k$.

\vspace{5mm}
\noindent
Similarly, we may repeat a $BPP$ algorithm, accepting if most of the
repetitions accept.
In both cases, the error probability drops dramatically (exponentially)
with the number of repetitions.

As a matter of fact,
by boosting the accuracy of probabilistic algorithms sufficiently,
we can relate the probabilistic complexity classes to 
circuit complexity classes, and to the polynomial hierarchy.

\section{BPP and P/poly}

\begin{theorem}
$BPP \subseteq$ P/poly.
\end{theorem}

\noindent
\textbf{Proof idea:} After boosting the accuracy of a $BPP$
algorithm sufficiently, we will show that some sequence 
$r \in \{0,1\}^{p(n)}$ of random bits works well for all inputs of
size $n$, and therefore is a good deterministic advice string.
Extending this idea to all possible input sizes, 
we will have a sequence of good advice strings, placing $L$ in
$P/poly$.

Rather than finding such a sequence of random vectors $r$ to
serve as a sequence of advice strings, we
give a non-constructive probabilistic proof of its existence.  
That is, if the fraction of sequences $r$ which are
good advice strings is
non-zero, (over all possible such sequences) then some such 
sequence exists.

\vspace{5mm}
\noindent
\textbf{Proof:}
Let $L$ be a language in $BPP$, decided by TM $M$ with error
probability $2^{-(n+2)}$.
(We can reduce the error by repetition while increasing 
the running time only polynomially.) That is,

\begin{equation*}
\begin{split}
\mbox{If } x \in L, \: Pr [ M(x,r) \mbox{ accepts } ] &\geq 1-2^{-(n+2)} \\
\mbox{If } x \not\in L, \: Pr [M(x,r) \mbox{ accepts } ] &\leq 2^{-(n+2)}
\end{split}
\end{equation*}

\noindent
Let us call a vector $r$ of random bits ``good for $x$'' if it causes
$M(x)$ to accept if $x \in L$ and to reject otherwise.
For a particular input $x$,

\begin{equation*}
\begin{split}
Pr [ r \mbox{ is good for } x ] &\geq 1 - 2^{-(n+2)} \\
Pr [ r \mbox{ is bad for } x ] &\leq 2^{-(n+2)}
\end{split}
\end{equation*}

\vspace{5mm}
\noindent
Now, the probability that $r$ is good for all inputs is simply

\begin{equation*}
\begin{split}
Pr [ r \mbox{ is good for all inputs } ]
&= 1 - Pr [ r \mbox{ is bad for at least one input } ] \\
&\geq 1 - \sum_x Pr [ r \mbox{ is bad for } x ]                  \\
&= 1 - ( \# \mbox{ of possible inputs } ) \cdot 2^{-(n+2)}             \\
&= 1 - 2^n \cdot 2^{-(n+2)}                                               \\
&= \frac{3}{4} \\
&\geq 0
\end{split}
\end{equation*}

\noindent
This shows that for any $n$, there exists a vector $r$ which is
good advice for all inputs of size $n$.  Collectively,
these vectors form a sequence of advice strings for $L$.
Thus, $BPP \subseteq P/poly$.

\vspace{5mm}
Note that $NP$ is not known to be contained in $BPP$.  If it were,
then the polynomial hierarchy would collapse to $\Sigma_2 P$, since
this containment would imply that $NP \subseteq BPP \subseteq P$/poly.  
In addition, if $NP \subseteq BPP$,
then $NP \subseteq RP$, implying that $NP = RP$.  ($RP \subseteq NP$
because of one-sided error.)  
We do know, however, that $BPP$ is contained in the second level of
the polynomial hierarchy.

\section{BPP and the Polynomial Hierarchy}

\begin{theorem}
$BPP \subseteq \Sigma_2 P \cap \Pi_2 P$
\end{theorem}

\noindent
\textbf{Proof idea:}  For any language $L$ in $BPP$, we will show that the 
statement $x \in L$ is equivalent to a quantified boolean formula
$ \exists y \forall z \phi (x,y,z) $,
for some appropriate variables $y, z$ and expression $\phi$.
Thus, we will show that 
$L \in \Sigma_2 P$, and since $BPP$ is closed under complement, 
that $L \in \Pi_2 P$ as well.

\vspace{5mm}
For any language $L$ in $BPP$, we know the following:

\begin{enumerate}
\item There is a TM $M$ that decides $L$ in probabilistic polynomial time 
with error probability $2^{-n}$ (by sufficient repetition).
\item $M$ makes decisions by choosing a random 
vector $r$
from the set $R = \{ 0,1 \}^{p(n)} $ for some polynomial $p$.
\item For a given input $x$, a subset $A_x$ of $R$
contains vectors $r$ that cause $M$ to accept $x$
(correctly or incorrectly).  The size of this subset satisfies
\begin{enumerate}

\item If $x \in L$, then $\frac{|A_x|}{|R|} = 1 - 2^{-n}$ 
%and $\frac{|B_x|}{|R|} = 2^{-n}$.

\item If $x \not \in L$ then $\frac{|A_x|}{|R|} 
%= \frac{B_x|}{|R|} 
= 2^{-n}.$

\end{enumerate}
\end{enumerate}

\vspace{5mm}
In order to create a quantified boolean formula
for $L$, we introduce the idea of translation of vectors.

\begin{definition}
Given strings $r$ and $t$, $|r| = |t|$, 
we define the translation of $r$ by $t$ 
to be $r \oplus t$, where $\oplus$ denotes the bitwise XOR operation.
Given set $S = \{r_1 ,..., r_k \}$, we define the translation of $S$ by $t$ 
to be
$S \oplus t = \{ r_1 \oplus t ,..., r_k \oplus t \} $.
\end{definition}

Now, we propose the following equivalence, from which the theorem
follows.
\begin{proposition}
For any language $L$ in $BPP$, $x \in L$ iff
there exists a set $S = \{ r_1 ,..., r_k \} $, all translations of which
contain at least one random vector $r_i$ which causes $M$ to 
accept $x$.  i.e. iff

\[
\exists S \: \forall t \:
[ (S \oplus t ) \cap A_x \not = \emptyset].
\]
where $k = p(n)$.

\end{proposition}

We will prove both the ``if'' and the ``only if'' directions
probabilistically, as we did for theorem 1.  
Keep in mind that if the fraction of sets $S$ satisfying the
proposition is non-zero (over all
possible such sets), then some such set exists.

\vspace{5mm}
\noindent
\textbf{Proof: }  $x \in L \Rightarrow \exists S \: \forall t \: 
[ (S \oplus t ) \cap A_x \not =  \emptyset]$ \\
Suppose $x \in L$.  We have the following string of equalities and
inequalities:

\begin{equation*}
\begin{split}
\underset{S}{Pr} [ \forall t : \: (S \oplus t) \cap A_x \not = \emptyset ] 
&= 1 - \underset{S}{Pr} [ \exists t : \: (S \oplus t) \cap A_x = \emptyset ] \\
&= 1 - \sum_t \underset{S}{Pr}[ (S \oplus t) \cap A_x = \emptyset ] \\
&\geq 1 - ( \# \mbox{choices for } t ) \cdot
\underset{S}{Pr}[ (S \oplus t) \cap A_x = \emptyset ] \\
&=1 - ( \# \mbox{choices for } t ) \cdot
\prod_{i=1}^{p(n)} \underset{r_i}{Pr}[(r_i \oplus t ) \not \in A_x ] \\
&=1 - 2^{p(n)} \cdot (2^{-n})^{p(n)} \\
&\gg 0.
\end{split}
\end{equation*}

\noindent
We conclude that when $x \in L$, $\exists S \: \forall t \: 
[(S \oplus t) \cap A_x \not = \emptyset]$.

\vspace{5mm}
\noindent
\textbf{Proof:} $x \not \in L \Rightarrow \forall S \: \exists t \: 
[( S \oplus t ) \cap A_x = \emptyset ]$. \\
Suppose $x \not \in L$.  We have the following string of equalities
and inequalities:

\vspace{5mm}
\noindent
Given a set $S = \{r_1 ,..., r_k \}$,
\begin{equation*}
\begin{split}
\underset{t}{Pr}[ (S \oplus t) \cap A_x = \emptyset ]
    &= 1 - \underset{t}{Pr}[ (S \oplus t) \cap A_x \not = \emptyset ] \\
    &= 1 - \sum_{r \in S} \underset{t}{Pr}[ r \oplus t \in A_x ] \\
    &\geq 1 - (|S|) \underset {t}{Pr}[ r \oplus t \in A_x]       \\
    &= 1 - k 2^{-n}                                                   \\
    &> 0 \quad \mbox{ for } k < 2^n.
\end{split}
\end{equation*}

\noindent
We conclude that when $x \not \in L$,
then for any set $S$, $|S| < 2^n$, $\exists t$ s.t.  
$[(S \oplus t) \cap A_x = \emptyset]$.

\vspace{5mm}
Thus we have shown that $BPP \subseteq \Sigma_2 P$, and since $BPP$ is closed
under complement, that $BPP \subseteq \Sigma_2 P \cap \Pi_2 P$.


%\bibliographystyle{abbrv}
%\bibliography{refs}

\end{document}