\documentclass{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphicx}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.5in}

\newcommand{\header}{
   \renewcommand{\thepage}{\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in {\bf 6.841/18.405J: Advanced Complexity \hfill Wednesday, Feburary 19th, 2003}
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill Lecture 5\hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it Instructor: Madhu Sudan \hfill Scribe: Steven Stern} }
      }
   }
   \end{center}
   \vspace*{3mm}
}

\newtheorem{theorem}{Theorem}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}

\begin{document}

\header

Problem Set 2 available today.  Due in 2 weeks, on March 5th.
\begin{enumerate}
    \item Polynomial Hierarchy
    \item $PH$ does not collapse?
    \item Circuit Complexity
    \item Karp-Lipton Theorem
\end{enumerate}

\section{Polynomial Hierarchy}

\subsubsection*{Definitions}
$\Sigma^P_i=$Languages accepted by polynomial time bounded $ATM$ starting in
existential state with $i$ alternating quantifiers.\\
$\Pi^P_i=$Languages accepted by polynomial time bounded $ATM$ starting in
universal state with $i$ alternating quantifiers.
$$PH=\bigcup_{i\geq0}\Sigma^P_i$$ $\Sigma^P_1=NP$, $\Pi^P_1=coNP$ and
by convention, $\Sigma^P_0=\Pi^P_0=P$.  $MINDNF\in\Sigma^P_2$ (this
was also shown to be complete for the class by Umans\cite{Umans1998}).

Since we can always add ``null'' quantifiers, we know that
$\Sigma^{P}_{i-1}\subseteq\Pi^{P}_{i}\subseteq\Sigma^{P}_{i+1}$.  We can also
define this class as $\Pi^{P}_{i}=\{\bar{L}|L\in\Sigma^{P}_{i}\}$.  Since $NP$
allows for one existential state, we can say that
$\Sigma^{P}_{i}=NP^{\Pi^{P}_{i-1}}$.

Furthermore, since $PH$ is an infinite union, we can also define it as
$PH=\bigcup_{i\geq0}\Pi^{P}_{i}$

\subsubsection*{Complete Problems}
There exists a complete problem for each of these classes, defined as follows:
$$i\exists TQBF=\{\phi|\exists x_{1}\forall x_{2}\exists
x_{3}...Q_{i}x_{i}\phi(x_{1},x_{2},...,x_{i})\}$$
$$i\forall TQBF=\{\phi|\forall x_{1}\exists x_{2}\forall
x_{3}...Q_{i}x_{i}\phi(x_{1},x_{2},...,x_{i})\}$$
where $\phi$ is a $3CNF$ formula, and $x_{1},x_{2},...,x_{i}$ are blocks of
variables.  $i\exists TQBF$ is $\Sigma^{P}_{i}$ complete, and $i\forall TQBF$
is $\Pi^{P}_{i}$ complete, for polynomial time reductions ($\forall i\geq1$)

\section{$PH$ does not collapse?}

We believe (but haven't proven) that $\Sigma^P_i\neq\Pi^P_i$, $\forall
i\geq1$.

\begin{center}
\includegraphics[scale=.5]{lect04-classes.eps}
\end{center}

{\theorem If $\Sigma^P_i=\Pi^P_i$, $\forall j\geq i$,
$\Sigma^P_j=\Pi^P_j=\Sigma^P_i$, and thus, $PH=\Sigma^P_i$.}\\

\noindent\textbf{Proof:} By induction on $j$.  True (by assumption) for $j=i$.
Let $j>i$ and assume true for $j-1$.

We know that $\Sigma^P_{j}$ contains every $TM$ $M$, where
$M$ makes $j$ alternating steps.  We can rewrite this as:
$$L=\{x|\exists y\text{ s. t. }N(x,y)\text{ accepts, where }N\text{ makes }j-1
\text{ alternating steps starting in a }\forall\text{ state}\}$$
But, since $\Sigma^P_{j-1}=\Pi^P_{j-1}$, there must exist $N'(x,y)$ which accepts the
same language as $N$, but makes $j-1$ alternations and starts in an $\exists$
state.
$$L(N')=\{(x,y)|\exists z\text{ s. t. }N''(x,y,z)\text{ accepts, }N''
\text{ makes }j-2\text{ alternations and starts in a }\forall\text{ state}\}$$
$$L=\{x|\exists y,z\text{ such that }N''(x,y,z)\text{ accepts}\}$$
$$L\in\Sigma^P_{j-1}$$

\section{Circuit Complexity / Non-Uniform Computation}

\subsubsection*{Circuit Complexity} How small a circuit can we build to decide
$SAT$?

We define circuits which take boolean inputs, of size $n$, and produce a
boolean output, of size $m$.  That is, $\{0,1\}^n\Rightarrow\{0,1\}^m$.  A
circuit is represented by a DAG (Directed Acyclic Graph), with the following
properties:

\begin{enumerate}
    \item n ``input'' vertices (have in-degree=0), labelled $x_1,x_2,...,x_n$.
    \item Many intermediate nodes (gates), of in-degree=1 (the NOT function) or
    in-degree=2 (the AND, OR functions).  If these have out-degree$=1$, it is
    called a formula.  If out-degree$>1$, it is a circuit.
    \item $m$ designated outputs.
    \item Size is defined as the number of gates.
\end{enumerate}

However, the circuit of interest to us is one that decides $SAT$.  That is, let $|\phi|=n$, and $SAT_n:\{0,1\}^n\Rightarrow\{0,1\}$, can we design a small
hardware circuit to solve this problem?

We define the complexity class corresponding to circuits as follows:

\begin{eqnarray*}
{\rm SIZE}(s(n)) &= \{ L | &\text{ There exists an infinite family of circuits }
C_1, C_2, \dots, C_n, \dots \text{ such that}\\
&&|C_i| \leq s(i), \forall i \text{ and } x \in L \iff C_{|x|} =1 \}
\end{eqnarray*} 
In other words, ${\rm SIZE}(s(n))$ is the set of all languages that
can be decided by a family of circuits of size $s(n)$.


\subsubsection*{Non-Uniform Complexity} Can a little ``advice'' help solve hard
problems?

For certain problems, this advice certainly can help.  The problem of deciding
if a $TM$ halts on the input $0^n$ can be decided with non-uniformity.
However, it is believed that no ``nice'' problems, such as $SAT$, can be
solved more efficiently with non-uniformity.

We define a $TM$ that uses non-uniformity as: $M(\bullet,\bullet)$, where the
first argument passed is the ``advice'', represented as a string, and the second
argument is the input.  There is a different ``advice'' string for each input
size.


\subsubsection*{Using a Circuit as the ``Advice''}

The interesting problem to examine is determining if there exist advice
strings, $a(1),a(2),...,a(n)$, such that $M(a(n),\phi)=1$ iff $\phi\in SAT$.
The running time of $M$ must be polynomial time, and the size of $a(n)$ must
be polynomial in $n$, for this problem to be interesting.  If either were
allowed to be exponential, then the problem becomes trivial.\\


\noindent\textbf{Definition:} $L\in P/poly$ if there exists a polynomial time
bounded Turning Machine, $M$, polynomial $p$, and advice strings
$a_1,a_2,...,a_n,...$ with $|a_n|\leq p(n)$ such that for every
$x\in\{0,1\}^n$, $x\in L\Leftrightarrow M(x,a_{|x|})=1$.

Note that $P/poly$ is exactly the class of languages that are
computable by a family of circuits of polynomial size. This
equivalence is noted by observing the following facts. (i) The circuit
can serve as the advice for each $n$. (ii) The advice for each $n$ can
be hardwired into the corresponding circuit. In other words, $P/poly =
\cup_{d\geq 0} {\rm SIZE}(n^d)$. 

\section{Karp-Lipton Theorem}

Clearly, if $P=NP$, the $SAT$ has polynomial sized cicuits, we'll show a
weak converse, namely that if $SAT $ has polynomial sized circuits,
then the polynomial hierarchy collapses. 
 
{\theorem $NP\not\subseteq P/poly\Rightarrow NP\neq P$, and $NP\subseteq
P/poly\Rightarrow$ $PH$ collapses to some finite level.  That is,
$PH=\Sigma^P_k$ for some finite $k$.}

First for some definition,

$$M\text{-}GOOD=\{a_n|\text{if }M(a_n,\bullet)\text{ decides }SAT\text{ on
}n\text{-length inputs}\}$$

The following two lemmata prove the above theorem.  

{\lemma Deciding if $a_n\in M$-$GOOD$ is in $\Pi^P_i$ for some $i$}

{\lemma if $NP\subseteq P/poly$ and $M$-$GOOD\in\Pi^P_i$ for some $i$,
then $\Sigma^P_{i+2}=\Sigma^P_{i+1}$}\\

\noindent Proof of Lemma 1: Observe that
$$a_n\in M\text{-}GOOD\iff \forall\phi,
\bigl(M(a_{|\phi|},\phi)=1\iff\exists\alpha, \phi(\alpha)=1\bigr).$$
Equivalently,
$$a_n\in M\text{-}GOOD\iff \forall\phi,
\biggl[
\bigl(
(M(a_{|\phi|},\phi)=1) \wedge (\exists \alpha, \phi(\alpha)=1)
\bigr) \vee
\bigl(
(M(a_{|\phi|},\phi)=0) \wedge (\forall \rho, \phi (\rho)=0)
\bigr)
\biggr]$$

Or equivalently,

$$a_n\in M\text{-}GOOD\iff\forall\phi,\rho\exists\alpha
\biggl[
\bigl(
(M(a_{|\phi|},\phi)=1) \wedge (\phi(\alpha)=1)
\bigr) \vee
\bigl(
(M(a_{|\phi|},\phi)=0) \wedge (\phi (\rho)=0)
\bigr)
\biggr]$$

and the above computation can be done in $\Pi^P_2$.\\

\noindent Proof of 2: Assume, for simplicity, that $i$ is odd.  By definition,
$(i+2)\exists TQBF=\{\phi|\exists x_1\forall x_2...\exists
x_{i+2}\phi(x_1,x_2,...,x_{i+2})\}$.  If we fix $x_1,x_2,...,x_{i+1}$, we can
examine $\psi(x_{i+2})=\phi(x_1,x_2,...,x_{i+2})$.  We will also use a
$M$-$GOOD$ string, $a_{n+1}$, and determine if $M(\psi,a_{n+1})=1$.  We are
going to guess an $M$-$GOOD$ string, and check it in parallel.  More formally:
\begin{quote}
$\Sigma^P_{i+1}$ computation for $\phi$:
\begin{enumerate}
    \item GUESS $x_1$,$a_n$
    \item FORALL 
	\begin{itemize}
	\item[] verify $a_n\in M$-$GOOD$
    	\item[] verify $\forall x_2\exists x_3...\forall x_{i+1}M(\psi,a_n)=1$, where
    $\psi(\bullet)=\phi(x_1,x_2,...,x_{i+2})$
	\end{itemize}
\end{enumerate}
\end{quote}

\begin{thebibliography}{10}

\bibitem[U98]{Umans1998} C. Umans. The Minimum Equivalant DNF
Problem and Shortest Implicants. In {\em Proceedings of the 39th
Annual IEEE Symposium on Foundations of Computer Science
(FOCS)}. pages 556-563. 1998.

\end{thebibliography}

\end{document}