\documentclass[10pt]{article} \usepackage{amsfonts,epsfig} %\usepackage{epsfig} \begin{document} \input{preamble.tex} \newtheorem{technique}[theorem]{Technique} \newtheorem{conjecture}[theorem]{Conjecture} \lecture{4}{Feb 20, 2007}{Madhu Sudan}{Katherine Lai} \section{Overview} In this lecture, we look at some lower bounds concerning the non-uniform forms of computation we discussed last time. \begin{itemize} \item Neciporuk's Theorem ($f\in P$ with BP size $\Omega((\frac{n}{\log n})^2)$) \item Barrington Construction of Small-Width BPs \end{itemize} \section{Previous Lecture} In the previous lecture, we discussed non-uniform forms of computation and their complexity measures.\\ \begin{tabular}{l|c|c|c|c|c} Nonuniform computation & \# bits of advice & time & size & width & depth\\\hline TM with advice & x & x & & \\ Circuits & & & x & & x \\ Branching Programs (BPs) & & & x & x & \\ Formulae & & & x & & x\\ \end{tabular} %$\log(width) \approx$ space We try to study these forms of computation to try to see what you can and can't solve with them, and in doing so divide up logspace and other classes. \section{Counting Technique} Before we discuss Neciporuk's theorem, we define the counting technique, which we will find useful. \begin{technique} Let ${\mathcal F} \subseteq \{f: \{0,1\}^n\rightarrow\{0,1\}\}$. Then $\exists f \in {\mathcal F}$ s.t. $size(f)\geq\Omega\left(\frac{log|{\mathcal F}|}{\log\log|{\mathcal F}|}\right)$. \end{technique} We can use this technique to count the number of functions circuits of a particular size can calculate. If we have circuits with size at most $s$, they can calculate $|{\mathcal F}|\leq2^{s\log s}$. However, if we wanted to use only this technique to prove anything meaningful about NP, it's never going to really work. NP is an infinite family of functions. For this concept to make sense, we would need to look at the first constant number of functions in NP, and we don't get anywhere if we use counting to find one function in NP. We will, however, see how we can get lower bounds with counting anyway. \section{Neciporuk's Theorem} %$$f\in P with BP size \Omega\left(\frac{n}{\log n}\right)^2$$ With Neciporuk's Theorem, we get a lower bound on the size of BP that calculates a function in P. First, we define the function. \begin{definition} Let $f:\{0,1\}^k\times \{0,1\}^{n-k}\rightarrow\{0,1\}$, with $f_x(i)=f(i,x)$. \end{definition} The question at hand is, how many different $f_x$ do we get? If all $f_x$'s are different, can we say anything about $size(f)$? We want to find out what the smallest circuit or BP we would need for this $f$. The key idea is if we have a circuit for $f$, we have a circuit for $f_x$--we just hardcode $x$ into the circuit. This doesn't increase the size of the circuit. If all $f_x$ are different, we have $${\mathcal F}=\{f_x\} \textrm{ with } |{\mathcal F}|\geq 2^{n-k}$$ $$size(f)\geq \frac{n-k}{\log(n-k)}=\Omega\left(\frac{n}{\log n}\right)$$ This result is unfortunately sublinear, so it doesn't tell us much yet. To construct ${\mathcal F}$ with a different $f_x$ for every $x$, we do the following. We set $f(i,x) = x_i$, where $x$ is the truth table where $x = x_1 \ldots x_{n-k}$, provided that $2^k\geq n-k$. \subsection{A superlinear lower bound} We want to find a superlinear lower bound, and to do this we have to restrict ourselves to only using BPs. We also need a metric for the size of the BP. \begin{definition} Let $BPSIZE_i(B)$ be the number of times the literal $x_i$ or its complement appears in the branching program $B$. \end{definition} % maybe include a diagram of example of a BP %% start node, two end nodes, outdegree of interior nodes = 2 with a %% literal and its complement. %% $BPSIZE_{1}$(of his example) = 2 %% because we see $x_1$ and $\bar{x}_1$ each once %% $BPSIZE_{1,3}$()=6 %% x1 !x1 %% !x2 x2 x2 !x2 %% !x3 x3 x3 !x3 %% 1 0 In the case of branching programs, we actually have a big advantage. Take subset $S\subseteq {1\ldots n}$ $BPSIZE_S(B)$ = \# edges labelled by literals of $S$ in the branching program $B$. To get a BP for $f_x$ from one for $f$, we simply fix the literals and shortcircuit some of the edges and erase other ones. If $f$ is a function on $n$ variables and $S_1, S_2\ldots S_l$ is a partition of the set $\{1\ldots n\}$, then $BPSIZE(f)\geq \sum_{i=1}^l BPSIZE_{S_i}(f)$ \begin{definition} Let the function Distinct? be defined as $$Distinct?(x_{11}\ldots x_{1k}, x_{21}\ldots x_{2k}, \ldots, x_{l1}\ldots x_{lk})=\left\{\begin{array}{l} 1 \textrm{ if } \forall j\neq k, i_j\neq i_k\\ 0 \textrm{ otherwise} \end{array}\right.$$ with $n=lk$. \end{definition} We would like to try to relate the lower bound to the number of bits. Take any block of variables. If we restrict the remaining variables, we get many different functions. There are $2^{k^{(l-1)}}$ ways to choose them all different for every set $T\subseteq \{1\ldots 2^k\}$ with $T={i_2f_1(i_1)=f(i1,i2,...il)\\ 0 \textrm{ if } i_1 \in T \end{array}\right.$$ The number of functions on $S_1$ is at least $$\left(\begin{array}{c}2^k\\l-1\end{array}\right) \approx \left(\begin{array}{c}2^k\\l\end{array}\right)\geq \left(\frac{2^k}{l}\right)^l$$ This is actually true for any $S_i$, so we get, by picking $k\geq 2\log l$, \begin{eqnarray*} BPSIZE_{S_i}(f)&\geq& \frac{\log(2^k/l)^l}{\log\log(2^k/l)^l}\\ &\geq& \frac{kl-l\log l}{\log(kl)}\\ &\geq& \Omega\left(\frac{n}{\log n}\right) \end{eqnarray*} Using the result from before, we have a total size \begin{eqnarray*} BPSIZE(f)&\geq& \sum_{i=1}^l BPSIZE_{S_i}(f)\\ &\geq&l\cdot\frac{n}{\log n}=\Omega\left(\frac{n}{\log n}\frac{n}{\log n}\right) \end{eqnarray*} and we achieve the desired superlinear lower bound. This may come in useful when we try to separate NP from NL or other complexity classes. In the next lecture, we'll see different examples of restricting other values. \section{Barrington Construction of Small width BPs} \subsection{Background} Roughly at stage of Neciporuk's Theorem, people were trying to separate NP from P or NL. Some thought that maybe looking at not just size, but size and width simultaneously, they would get some result. They hoped the following would be true. \begin{proposition} If $f\in P$ needs large width branching programs (super polynomial), then $P \neq L$. \end{proposition} The problem with this, however, is whether we can prove super polynomial large widths. Given any DNF formula, it is trivial to construct a BP for it with only three branches. For example, if we have the DNF formula $x_1x_2x_3 \vee \bar{x}_1x_3x_4 \vee x_2 \bar{x}_3 x_5$, the BP can sequentially try every term and branch between two of the branches, exiting to the third branch if it is clear that the whole formula will be satisfied already. Since any formula for $f\in P$ can reduce to a DNF formula, no $f$ needs super polynomial width. This leads to the next idea. \begin{proposition} If $\exists f \in P$ that needs large branching programs-- super polynomial width or super polynomial size then $P\neq L$. \end{proposition} This turns out to be true, but we still don't know how to prove super polynomial size. We will instead pursue a weaker goal: we will try to find $f\in P$ that requires super constant width or super polynomial size. (This doesn't actually prove anything.) \begin{proposition} The function $$Majority(x_1\ldots x_n) = \left\{\begin{array}{l}1 \textrm{ if }\sum x_i \geq n/2\\ 0\textrm{ otherwise}\end{array}\right.$$ requires super constant width if the size is polynomial. \end{proposition} \begin{theorem} Barrington's Theorem: Let $f$ be a function that has a depth $d$ formula over \{binary AND, NOT\}. Then $f$ has a BP of width 5 (we will prove 8 today) and depth $4^d$. It has a log-depth formula, so it has a polynomial-sized BP. \end{theorem} \subsection{Register Machine} To prove Barrington's theorem, we will be using a register machine [Ben-Or,Cleve]. A register machine consists of $l$ registers, $R_1, \ldots, R_l$, each of which stores one bit. The register machine is fed a set of instructions $I_1,\ldots, I_S$ that describe how to update the registers. For example, $I_2$ might be $R_1 \leftarrow R_2 + x_i\cdot R_3$. The end result is then some linear combination of the registers. If a register machine takes $(R_1\ldots R_l) \rightarrow (R_1\ldots R_{(l-1)}, R_l+f(x_1\ldots x_n)\cdot R_1)$, then this machine is said to compute $f$. This can be done by setting the registers to $(1, 0, \ldots, 0)$ initially. This leaves the first $l-1$ registers the same and the answer in $R_l$. \begin{fact} If an $l$-register machine of size $S$ computes $f$, then $\exists BP$ of width $2^l$ and size $O(S)$. \end{fact} The width comes from needing to remember all registers, of which must have at least $2^l$ states. To prove the BP of width 8, we will thus need a 3-register machine. \subsection{Ben-Or Cleve Induction} If $f$ has depth $d$ formula over \{binary NOT, AND\}, then $f$ is computed in size $4^d$ by a 3-register machine. %% R1 arrow to new R3, labelled with f R1 %% R2 R2 %% R3 R3+f*R1 %% $$f(x)=\neg g(x)$$ %% $$R_3 \oplus R_1 (1 \oplus g(x))$$ %% $$R_3+R_1+g(x)*R_1$$ %% $$I=R_3 <- R_3 + R_1$$ %% so this (negation function) is taken care of %% $f = f_1 \wedge f_2$ %% $f_1$ and $f_2$ both have depth $d$, so $f$ has depth $d+1$ %% first compute f1 %% R1 R1 R1 R1 R1 %% R2 R2 R2+f2(R3+f1R1) R2+f2R3+f1f2R1 R2+f1f2R1 %% R3 R3+f1R1 R3+f1R1 R3 R3 %% arrow goes from R1 to R3, %% R3 to R2 %% R1 to R3 %% R3 to R2 To calculate NOT, or $\neg f_1$ for some $f_1$, we use the following register machine. The instructions are: \begin{center} \begin{tabular}{ll} $I_1$: & $R_3 \leftarrow R_3 + f_1R_1$\\ $I_2$: & $R_3 \leftarrow R_3 + R_1$ \end{tabular} \end{center} \noindent which leaves the first two registers unchanged, and changes $R_3$ to contain the value $r_3+(1+f_1)r_1$, where $r_1$ and $r_3$ are the initial values in registers $R_1$ and $R_3$ respectively. We can then obtain the value $\neg f_1$ from the result in $R_3$. \fig{not}{0pt}{Diagram of a BP used for a NOT operation}{not.eps} To calculate AND between $f_1$ and $f_2$, it is somewhat more complicated. We use the following instructions for the register machine: \begin{center} \begin{tabular}{ll} $I_1$: & $R_3 \leftarrow R_3 + f_1R_1$\\ $I_2$: & $R_2 \leftarrow R_2 + f_2(R_3 + f_1\cdot R_1)$\\ $I_3$: & $R_3 \leftarrow R_3 + f_1R_1$\\ $I_4$: & $R_2 \leftarrow R_2 + f_2R_3$\\ \end{tabular} \end{center} \noindent If we let the initial values in the registers be $r_1$, $r_2$, and $r_3$, we see that $I_3$ had the effect of restoring $R_3$ to its original value $r_3$, and $I_4$ cancelled out the $f_2r_3$ term, so that in the end, $R_2$ contained $r_2+f_1f_2r_1$. \fig{and}{0pt}{Diagram of a BP used for an AND operation}{and.eps} \subsection{Conclusions} At the end of Barrington's results, there were many objects coming together and looking identical--log-depth circuits, formulas, polynomial size and bounded width BPs, and so on. Counting has not worked to show if circuits and formulae are different. In actuality, the conjecture mentioned earlier is false. We know functions that require super polynomial size, but they're not in PSPACE, and the question is how far away that is. Relatedly, the complexity class ``Nick's class'' $\textrm{NC}^i$ is for circuits of depth $\log^in$, and it is named after Nick Pippenger. \end{document}