\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}