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

\begin{document}
\lecture{6}{February 26, 1998}{Dan Spielman}{Matthew Levine} 

\section{Diagonalization and NP}
The main result of this lecture is the following theorem:

\begin{theorem}
  [Baker-Gill-Solovay] There are oracles $A$ and $B$ such that \\
  a) $P^A = NP^A$ and  \\
  b) $P^B \neq NP^B$
\end{theorem}

This theorem is interesting, because it rules out many approaches for
trying to resolve the question of whether $P = NP$ or not.  In
particular, many proofs that two complexity classes are different use
a diagonalization argument, where one constructs a member of one class
that is explicitly different from each object of the other class.  For
example, it is possible to prove that the halting problem is not
computable in this way. People thought this technique might work to
prove $P \neq NP$, but diagonalization arguments tend to hold relative
to an oracle, so the first half of the above theorem shows that this
is not possible. Likewise, it is unlikely that we can show $P=NP$ by
an argument that a $P$ machine can simulate an $NP$ machine, because
that too would probably hold relative to an oracle, contradicting the
second half of the theorem. The bottom line is that any proof
regarding the $P = NP$ question must {\em not\/} hold relative to an
oracle, or it will contradict the theorem. This suggests that
resolving the $P$ versus $NP$ question will be difficult.

We now give the proof.

\subsection{Part a}

To show the first part of the theorem, we need to construct an oracle
$A$ such that $P^A=NP^A$, that is, an oracle where nondeterminism
won't add any power. Since $NPSPACE = PSPACE$, an oracle for 
a $PSPACE$-complete problem seems like a good idea.

Recall that the language of true quantified boolean formulas ($TQBF$)
is $PSPACE$-complete under polynomial time mapping reductions. (A
quantified boolean formula is an expression of the form $\exists x_1
\forall x_2 \forall x_3 \exists x_4 \ldots {\rm boolean\
  formula}(x_1,x_2,\ldots,x_n)$) Let $A$ be an oracle for $TQBF$.

We have that $NP^A \subseteq NPSPACE$, because an $NPSPACE$ machine
can easily simulate an $NP$ machine, and can simulate the $TQBF$
oracle, without using nondeterminism. 
We also have $PSPACE \subseteq P^A$, because $TQBF$ is a
complete problem for $PSPACE$. Since $NPSPACE = PSPACE$, this gives
$NP^A \subseteq P^A$. It is obvious that $P^A \subseteq NP^A$, so in
fact $P^A = NP^A$.

\subsection{Part b}

To show this part of the theorem, we want to construct an oracle
$B$ and a language $L$ such that $L \in NP^B$, but $L \notin P^B$.  We
start by defining a language associated with an oracle $B$:
$$L(B) = \{ x | \exists y \in B \mbox{~~s.t.~~} |y| = |x| \}$$
So $L(B)$ contains
all strings of the same length as some element of $B$. (Think of $B$
as a set of the strings that it accepts.)  Observe that $L(B) \in
NP^B$, because on input $x$ an $NP$ machine can guess a $y \in B$ such
that $|x|=|y|$ and then check with one call to $B$.

Now we want to construct $B$ so that no deterministic polynomial time
machine can accept $L(B)$. The idea is that on an input of length $n$
there are $2^n$ possible strings that could be in $B$, and the
deterministic machine has no way to tell which except by trying them
all. 

We start by showing that for any fixed deterministic polynomial time
oracle Turing machine $M^?$, we can construct a $B$ such that $M^B$
cannot accept $L(B)$. We will then show how to construct such a $B$
for all such $M^?$ at once.

By the definition of running in polynomial time, there exists an $n$
such that $M$ runs in time less than $2^n$. Since there are $2^n$
$y$'s of length $n$, on input $0^n$ $M^\emptyset$ doesn't query $B$ about
some $y$. Therefore, if $M^\emptyset$ accepts $0^n$ we can set
$B=\emptyset$, and $M^B$ will make a mistake testing membership in
$L(B)$. Likewise, if $M^\emptyset$ rejects $0^n$ we can set $B=\{ y \}$,
and $M^B$ will make a mistake testing membership in $L(B)$.

We extend this by a diagonalization argument: we will enumerate the
deterministic polynomial time Turing machines and arrange to trick
each one for a different length input. This will succeed in tricking
them all.
 
There exists an enumeration of polynomial time oracle Turing machines.
Consider the enumeration $M^{?}_{1}$, $M^{?}_{2}$, $M^{?}_{3}$, \ldots

The following ``algorithm'', gives the construction of $B$:

\begin{enumerate}
\item Let $B_0=\emptyset$, $n=0$
\item for $i=1,2,3,\ldots$ do
\begin{enumerate}
\item   choose $n_i>n$, such that $M^{B_{i-1}}_i$ on input $0^{n_i}$
        asks fewer than $2^{n_i}$ questions.
\item   If $M^{B_{i-1}}_i$ accepts $0^{n_i}$ then
            let $B_i=B_{i-1}$ (don't include any new strings) \\
        Else (it rejects) let $B_i=B_{i-1} \cup \{x$ s.t. $|x|=n_i$
            and $x$ was not asked about by $M^{B_{i-1}}_i\}$.
\item   set $n=\max_i\{$length of longest query asked by
  $M^{B_{i-1}}_i,$  on input $0^{n_{i}} \}$.
\end{enumerate}
\item set $B=\bigcup_{i=0}^{\infty}B_i$
\end{enumerate}

It is clear that $L(B) \notin P^B$, because each $M_i^B$ gives the
wrong answer on $0^{n_i}$. Therefore $P^B \neq NP^B$.

\end{document}