\documentstyle{article}  % [12pt, times, doublespace]
%\usepackage{amsmath, amssymb}
\input{preamble.tex}

\begin{document}

\lecture{4}{February 10, 2000}{Dan Spielman}{David Manz}

\section{Review}

We are discussing the definitions of the polynomial hierarchy.  The first 
thing to do in this lecture is to show that Definition 3 is equivalent to 
Definition 1.  To review, the definitions are:

\begin{description}

\item[Definition 1]

$\Sigma_{k}P = $ a language L that is recognized by an ATM, which begins 
in an $\exists$ state and alternates at most $k-1$ times.

\item[Definition 3]

$\Sigma_{k}P = NP^{TQBF_{k-1}^{\forall}} = NP^{TQBF_{k-1}^{\exists}}$

\end{description}

\section{Equivalence of Definitions}

{\bf Terminology Note:}\\
$QBF$ is a set of things, $TQBF$ is the language of true $QBF$s.\\
$QBF_{k}^{\exists}$ is a set of things, $TQBF_{k}^{\exists}$ is the language of true $QBF_{k}^{\exists}$s.

\begin{theorem}Definition 1 $\subseteq$ Definition 3\end{theorem}

%We gave $TQBF_{k}^{\exists(\forall)}$ complete for $\Sigma_{k}P$ ($\Pi_{k}P$)

\begin{claim}
$TQBF_{k}^{\exists} \subseteq NP^{TQBF_{k-1}^{\forall}}$
\end{claim}

\begin{proof}
Consider a $QBF_{k}^{\exists}:  \exists x_{1} \forall x_{2} \ldots \exists 
x_{k}  A(x_{1}, x_{2}, \ldots x_{k})$.  The NP machine can guess an 
assignment for $x_{1}$ and accept if $A(\underline{x_{1}}, x_{2}, \ldots x_{k})
\in TQBF_{k-1}^{\forall}$, which is determined by a call to the 
oracle.
\end{proof}

\begin{theorem}Definition 1 $\supseteq$ Definition 3\end{theorem}

The problem is that a NOTM $M^{?}$ can ask the oracle many questions.  We
need to condense this down to just one question.  First, we will prove the 
special case, $NP^{TQBF_{1}^{\forall}} \subseteq \Sigma_{2}P$ (this is co-SAT).

\begin{claim}We can combine instances of calls to a $TQBF_{1}^{\forall}$ 
oracle.\end{claim}

We want to know if $\forall \overline{x} \Phi(x)$ is true ($\Phi(x)$ is some 
boolean formula).  However, we also want to find out if $\Theta(y)$ is true.
We can ask both as:
$\forall \overline{x}, \overline{y} (\Phi(x) \bigwedge \Theta(y))$.  This is
not enough to prove the theorem.  There are two problems with this approach:
\begin{enumerate}
\item {\bf Problem:} It could be that $M^{?}$ accepts {\it iff} first is true and second
is false  ($\neg \forall y \Theta(y) \rightarrow \exists y \neg \Theta(y)$)\\
{\bf Solution:}  We want to know $\forall x \Phi(x) \bigwedge \exists y (\neg 
\Theta(y))$.  The NP machine can guess y.

\item {\bf Problem:} We don't know the questions in advance, and one can depend on another.\\
{\bf Solution:} Guess what all questions to the oracle will be, and guess their
answers;  simulate the original machine, reject if you guessed the wrong 
questions, else use your answers guessed.  At the end, we need to verify the
answers and accept if they were correct and the simulated machine accepted.
So, we get a polynomial number of questions and answers to verify.  We need to
verify
$\forall x \Phi_{1}(x) \bigwedge
\forall x \Phi_{3}(x) \bigwedge \ldots
\forall x \Phi_{k}(x) \bigwedge
\neg (\forall x_{2} \Theta(x)) \bigwedge \ldots
\neg (\forall x_{j} \Theta)$
\end{enumerate}.  The formulae subject to the universal quantifiers can be 
lumped together with ANDs, and a negated universal formula translates into
the equivalent existential expression with the formula negated (as described
in the solution to the preceding problem).

Now for the general case.
\begin{claim}$NP^{TQBF_{k-1}^{\forall}} \subseteq \Sigma_{k} P$.\end{claim}
We did $k=2$.  In the general case, the first step of combining ``yes'' 
instances is fine, so we just have to get answers to $QBF_{k-1}^{\exists}$.  
We will use the NP OTM to guess first quantifier, and then the rest gets 
globbed into the one question--we do a lot of pre-guessing and then reject 
where guesses were incorrect.

\section{Circuit Complexity}

\begin{definition}
For a function $f:\{0,1\}^{n} \rightarrow \{0,1\}^{b}$ the circuit complexity
of $f$, $C(f)$, is the least $m$ such that there exists a circuit (boolean,
binary, $\bigvee$, $\bigwedge$, $\neg$) with $m$ gates that computes $f$.
\end{definition}

%\begin{definition}
%A language L has polynomial circuit complexity if there exists $k$ such
%that the functions
%
%$f_{n}: \{0, 1\}^{n} \rightarrow \{0, 1\}$\\
%$f_{n}(x) = 
%   \left\{ \begin{array}{l} 
%	1 {\rm if} |x| = n {\rm and} x \in L\\
%	0 {\rm otherwise}
%\end{array} \right.$\\
%$C(f_{n}) = O(n^{k})$
%\end{definition}

\begin{definition}
A language L has polynomial circuit complexity if there exists $k$ such
that the functions 
  $f_{n}: \{0, 1\}^{n} \rightarrow \{0, 1\}$ such that
\[f_{n}(x) = 
   \left\{ \begin{array}{l} 
        \hbox{1  $|x| = n$  and $x \in L$}\\
        \hbox{0  otherwise}
\end{array} \right. 
\]\\
\[C(f_{n}) = O(n^{k}) 
\]
\end{definition}


\begin{theorem}(Karp-Lipton-Sipser)\\
If an NP-complete language has polynomial circuits, then $\Sigma_{2}P = \Pi_{2}P$.\end{theorem}

\begin{definition}$L \in P/poly$ if there exists a constant $k > 0$ and
an infinite sequence of strings $\{S_{i}\}_{i \in N}$ and $A \in P$
and $|S_{i}| = O(i^{k})$ such that $w \in L \leftrightarrow (w, S_{|w|})
\in A$. ($S_{i}$ is an ``advice string'')\end{definition}

\begin{proposition}
$L \in P/poly \leftrightarrow$ P has polynomial circuit complexity.
\end{proposition}

\begin{proof}$\leftarrow$\\
Let $S_{i}$ be an encoding of a circuit that computes $f_{n}$ of size
$O(n^{k})$ and $A = \{(w, S)$ such that the circuit encoded by $S$ accepts
string $w$\}.\end{proof}

\begin{proof}$\rightarrow$\\
Consider M that accepts A.  Consider the computation tableau of M accepting
A, convert it into a circuit (a different circuit for each different size
input), and hardwire in the advice string, S.\end{proof}

\begin{theorem}
If $NP \subseteq P/poly$, then $\Sigma_{2} P = \Pi_{2} P$.
\end{theorem}

\begin{proof}
$NP \subseteq P/poly \rightarrow SAT \subseteq P/poly \rightarrow
\exists k, A \in P, \{S_{n}\}_{n \in N}$ such that $|S_{n}|
\leq (kn)^{k}$ and $w \in SAT \leftrightarrow (w, S_{|w|}) \in A$.
\end{proof}

\begin{definition}
Let $(g_{1}, \ldots g_{l})$ be a sequence of strings.
$(g_{1}, \ldots g_{l})$ is \underline{good} if:\\
\begin{enumerate}

\item $|g_{i}| \leq (ki)^{k}$
\item $\forall w: |w| \leq l,\\
	w \in SAT$ {\rm iff} $(w, g_{w}) \in A$

\end{enumerate}
\end{definition}

\section{For Next Time}

Define $GOOD =$ the language of {\it good} strings.

What is the complexity of $GOOD$?

$GOOD \in \Pi_{1} P = co\-NP$

First, prove $GOOD \in \Pi_{2} P$  (easy)

\end{document}