\documentclass[11pt]{article} \usepackage{amsfonts} \usepackage[dvips]{graphicx} \newtheorem{define}{Definition} %\newcommand{\Z}{{\bf Z}} %\usepackage{psfig} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \begin{document} \input{preamble.tex} \lecture{14}{March 28, 2005}{Madhu Sudan}{Alissa Reyzin} \section{Today} \subsection{Announcements} \begin{itemize} \item Have you scribed twice? Please sign up to scribe if you haven't. \item Pick up graded problem set 2 from Sergey \end{itemize} \subsection{Toda's Theorem} \begin{itemize} \item Recall operators $\exists$, $\forall$, $\bigoplus$, $BP$ \item Operator Calculus $PH \subseteq BP \cdotp \bigoplus \cdotp P$ \item Arithmetic $BP \cdotp \bigoplus \cdotp P \subseteq P^{\#P} $ \end{itemize} Although Toda's Theorem is very powerful, we still do not know whether $\#$P is different from PSPACE. We also do not know whether it is different from LOGSPACE. \section{Applying Operators to Complexity Classes} Given a complexity class $C$ and an operator $O$ we can construct a new complexity class $O \cdotp C$. For example, we have already seen that: \begin{itemize} \item $\exists \cdotp P = NP$ \item $\exists \cdotp co$-$NP = \Sigma_2^P$ \item $\forall \cdotp \Sigma_2^P = \Pi_3^P$ \end{itemize} Remember that the operator $\bigoplus$ gives us an exact count on the least significant digit and the operator $BP$ gives an approximate count on the total. The precise definitions of the operators are as follows. \begin{itemize} \item A language $L \in \exists \cdotp C$ if there exists a machine $M$ such that $L(M) \in C$ and $L = \{x | \exists y$ such that $M(x, y) = 1\}$. Keep in mind that the running time complexity for all classes created by operator applications must be measured as a function of the first input, since the later inputs can be extremely large. \item A language $L \in \bigoplus \cdotp C$ if there exists a machine $M$ such that $L(M) \in C$ and $ L = \{x| $ the number of $y$'s such that $M(x, y) = 1$ is odd $\}$. Consider what happens if we replace the word ``odd'' with ``even''. This gives us the class $co \bigoplus \cdotp P$. We can easily see that this class is the same as $\bigoplus \cdotp P$. Consider $M'(x, by) = $ accept if $by = \bar{0}$ or if $b = 1 $ and $M(x, y)$ accepts. This has exactly one more accept than $M(x, y)$. \item We use the strong definition of BP when defining the operator. The distinction is important, since we are not guaranteed to be able to amplify when the operator is attached to a given complexity class. A language $L \in BP \cdotp P$ if $\forall$ polynomials $q$ there exists a machine $M$ such that $L(M) \in C$ and $\mbox{Pr}_y[M(x, y) = ``x \in L''] \geq 1 - \frac{1}{2^{q^{|x|}}}$ \end{itemize} \section{Proof of $PH \subseteq BP \cdotp \oplus \cdotp P$} To show that $PH \subseteq BP \cdotp \bigoplus \cdotp P$ we need the following steps. \begin{eqnarray} \mbox{(we can also show this for the $\forall$ operator) } \exists \cdotp BP \cdotp \oplus \cdotp P \subseteq BP \cdotp \oplus \cdotp BP \cdotp \oplus \cdotp P\\ \subseteq BP \cdotp BP \cdotp \oplus \cdotp \oplus \cdotp P \\ \subseteq BP \cdotp \oplus \cdotp \oplus \cdotp P \\ \subseteq BP \cdotp \oplus \cdotp P \end{eqnarray} After this has been shown, we can use induction to demonstrate that any constant length sequence of $\forall$ and $\exists$ quantifiers can be absorbed into the class $BP \cdotp \bigoplus \cdotp P$. \subsection{Step 4} We need to show that $\bigoplus \cdotp \bigoplus \cdotp C \subseteq \bigoplus \cdotp C$ Let $L(M) \in C$ Let $L_1 = \{(x, y) | $the number of $z$ such that $M((x, y), z)$ accepts is odd $\}$. Then $L_1 \in \bigoplus \cdotp C$. Let $L_2 = \{x | $ the number of y such that $(x, y) \in L_1$ is odd $\}$ \begin{figure}[!h] \begin{center} \includegraphics[scale=.5]{plusplus.ps} \end{center} \end{figure} We can draw the circuits using parity operators for the above languages. We see that all we need to show is that $\sum_y \sum_z M(x, y, z) = \sum_{(y, z)} M(x, y, z)$. But this is obvious. The only small caveat is that we need to have associativity. That is $M((x,y) z) = M(x, (y, z))$. We also need to have available linear time in order to reparenthasize. \subsection{Step 3} We need to show that $BP \cdotp BP \cdotp P \subseteq BP \cdotp P$. The main idea is that instead of calculating approximate majority first over all the $y$'s and then over all the $z$'s we do it over all pairs $(y, z)$ which will at most sum the two error probabilities. \begin{figure}[!h] \begin{center} \includegraphics[scale=.5]{bpbp.ps} \end{center} \end{figure} That is, we draw a circuit with $BP$ gates. Assume that the error we want in our final circuit is $2^{-q(n)}$. Then we simply pick our $BP$ gates in the original circuit to have error $2^{-q(n) + 1}$. At worst, the probabilities of error will be added together, which gives us the desired probability. \subsection{Step 2} We need to show that $\bigoplus \cdotp BP \cdotp C \subseteq BP \cdotp \bigoplus \cdotp C$. \begin{figure}[!h] \begin{center} \includegraphics[scale=.5]{plus.ps} \end{center} \end{figure} Let us call the fan out of the parity gate $2^l$ and the fanout of the BP gate $2^m$. Suppose for a moment that the BP gate made no errors. In that case, clearly, the switch is a valid one. Every error made can give the wrong output of the parity gate. How many errors do we have? $2^l * 2^m * 2^-q = 2^{l + m - q}$. Now consider the number of parity gates computing the wrong value after the switch. This is also at most $2^{l + m - q}$. Therefore, the probability of error is $\frac{2^{l + m - q}}{2^m} \leq 2^{l-q}$. So, if we want $q'(n)$ to be the probability of error, we simply choose $q(n) = q'(n) + l$. Note that this does not work in the reverse direction, since each parity gate may have errors. \subsection{Step 1} We need to show that $\exists \cdotp C \subseteq BP \cdotp \bigoplus \cdotp P$ where $C = BP \cdotp \bigoplus P$. (This does not hold true for all complexity classes, since we need to be able to use amplification.) \begin{figure}[!h] \begin{center} \includegraphics[scale=.5]{vbp.ps} \end{center} \end{figure} Where have we seen a similar picture before? This looks a great deal like the Razborov-Smolensky proof. Unfortunately, picking a random subset of an exponential number of things costs us too much time. It is possible to use pseudo-randomness instead of true randomness, but this requires techniques that we haven't seen. Instead, we will try to use Valiant-Vazirani (Unique SAT in Parity SAT). The problem with using Valiant-Vazirani is that the error is too high. On the other hand, the error is one sided, which makes amplification easier. Valiant-Vazirani gives us: \begin{itemize} \item $\phi \mbox{ satisfiable} \rightarrow \phi' \mbox{ odd}$ with probability $1/n$ \item$\phi \mbox{ unsatisfiable} \rightarrow \phi' \mbox{ even}$ with probability 1. \end{itemize} What we want is: \begin{itemize} \item$\phi \mbox{ satisfiable} \rightarrow \phi' \mbox{ odd}$ with probability $1-2^{-n}$ \item$\phi \mbox{ unsatisfiable} \rightarrow \phi' \mbox{ even}$ with probability $1-2^{-n}$. \end{itemize} Let's complement everywhere. That is, let's have a satisfiable $\phi$ go to an even $\phi'$ and an unsatisfiable $\phi$ go to an odd $\phi'$. Then, we can calculate $\phi'_1, \phi'_2, \phi'_3 ...$ which will be completely independent variables. Since $\#$SAT = product of $\#$SAT, we know that if all of the $\phi'_i$ are odd, the product will be odd, otherwise it will be even. This gives us exactly the amplification we were looking for. Since all that we used to do the amplification was complementation and polynomial time manipulations, this shows that $\exists$ can be replaced as stated above. \section{Proof of $BP \cdotp \oplus \cdotp P \subseteq P^{\#P}$} We need to show that $BP \cdotp \oplus \cdotp P \subseteq P^{\#P}$ $\bigoplus \cdotp P \subseteq \{(\phi, t, N) |$ the number of accepting configurations$ \in \{0, 1\} (\bmod N)\}$. We accept if the number of accepting configurations is 0 mod 2 and reject if it is 1 mod 2. What happens if instead of 2 we use $2^N$ where $N$ is large? If $x$ is in the language $L$, then the number of accepting configurations is $\leq 2^{m-q} \pmod 2^N$. If $x$ is not in $L$ then the number of accepting configurations is between $2^m - 2^{m-q}$ and $2^m \pmod 2^N$. Unfortunately, we can't actually do this. However, we can accept if the number of accepting configurations is 0 mod 2 and reject if it is -1 mod 2. This will leave the intervals disjoint, which is sufficient for us. \subsection{Arithmetic with Counting Functions} $f: \Sigma^* \rightarrow \mathbb{Z}$ is a counting function if $\exists M \in P$ such that $f(x) = \#$ y's such that $M(x, y) =1 $. We show that if $f_1$ and $f_2$ are counting functions, then so are $f_1 \cdotp f_2$ and $f_1 + f_2$. This is easy to see. To get a TM that that accepts $f_1 \cdotp f_2$ things given a TM $M_1$ that accepts $f_1$ things and a TM $M_2$ that accepts $f_2$ things we simply put the two ``in series''. That is, for branch of $M_1$ that accepts, we then run the the machine $M_2$ on $x$. To get a TM that accepts $f_1 + f_2$ things, we flip a coin. depending on the result of the coin flip, we either run $M_1$ or $M_2$. $h: \mathbb{Z} \rightarrow \mathbb{Z}$ is a polynomial with non-negative coefficients. If $f$ is a counting function, clearly so is $h(f)$ by the above. We come up with a clever polynomial $h = 3f^4 + 4f^3$. If $f$ has 0 accepting configurations modulo $2^k$ then $h(f)$ will have 0 accepting configurations modulo $2^{2k}$. Moreover, if $f$ has 1 accepting configuration modulo $2^k$ then $h$ will have $-1$ accepting configurations modulo $2^{2k}$. We then need to apply the process log $n$ times in order to actually get something with the correct properties modulo $2^N$ (which we can actually do in the correct time bound). Reference the slides to see how to come up with the polynomial $h(f)$ that works. \end{document}