\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{fullpage}
\input{preamble.tex}

% For pretty pictures
\usepackage{tikz}
\usetikzlibrary{trees,positioning,arrows}

% some definitions
\def\PH{\textsf{PH}}
\def\P{\textsf{P}}
\def\NP{\textsf{NP}}
\def\sharpP{\textsf{P$^{\textsf{\tiny \#P}}$}}
\def\xor{\mathop{\oplus}\cdot}
\def\BP{\textsf{BP}\cdot}
\def\M{M(x,y,z)}
\def\xnor{\overline{\oplus}\cdot}
\def\st{\text{ s.t. }}
\def\ie{\textit{i.e.}~}
\newcommand{\imod}[1]{~\mathrm{mod}~#1}
\newcommand{\PR}[2][]{\Pr_{#1}\left[#2\right]}
\newcommand{\case}[1]{\vskip .3cm\textsc{#1}\hskip 0.5cm}

\begin{document}

\lecture{13}{March 18, 2009}{Madhu Sudan}{Alex Cornejo}

\section{Overview of today's lecture}
\begin{itemize}
  \item Toda's Theorem: $\PH :=\bigcup_{k \in \mathbb{N}} \sum_k^P \subseteq \sharpP$, steps:
  \item Prove some properties concerning $\exists C$, $\forall C$, $\xor C$, $\BP C$
  \item Do some operator calculus to prove $\PH \subseteq \BP \xor\P$.
  \item Prove that $\BP\xor \P\subseteq \sharpP$
\end{itemize}

\section{Review: Operator definitions}

\def\q{{q(n)}}
\def\p{{p(n)}}
Let $L$ be a language, $C$ a complexity class and $\q$ some growing
function of $n$.
\begin{align*}
  \textsf{BP}_\q\cdot L &= \set{\Pi^\q_{yes}(L),\Pi^\q_{no}(L)} \\
  \Pi^\q_{yes}(L) &= \set{x \mid \PR{(x,y) \in L} \ge 1-2^{-\q}} \\
  \Pi^\q_{no}(L) &= \set{x \mid \PR{(x,y) \in L} \le 2^{-\q}}
\end{align*}

When we omit the $\q$ subscript we assume that $\q \in \P$.

\begin{align*}
  \BP L &= \set{\Pi_{yes}(L),\Pi_{no}(L)} & \BP C &= \set{\BP L \mid L \in C } \\
  \xor L &= \set{x \mid \#(y) \st (x,y) \in L \text{ is even}} & \xor C &= \set{\xor L |  L \in C} \\
  \xnor L &= \set{x \mid \#(y) \st (x,y) \in L \text{ is odd}} & \xnor C &= \set{\xnor L |  L \in C} \\
  \exists \cdot L &= \set{x \mid \exists y \st (x,y) \in L} & \exists \cdot C &= \set{\exists \cdot L |  L \in C} \\
  \forall \cdot L &= \set{x \mid \forall y \st (x,y) \in L} & \forall \cdot C &= \set{\forall \cdot L |  L \in C} \\
\end{align*}

For this lecture, the correct way to think about an expression
involving Toda's complexity operators is visualizing the execution tree
that represents the expression. For example consider a language $L \in \BP
\xor \P$, then for $x \in L$ we have the following
tree:

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=2.5cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{xor}=[shape=circle,text centered, draw=black, inner sep=-1.6pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(root)[bag]{\textsf{BP}}
      child {
        node(l1a)[xor] {\LARGE +}
        child{node(l1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$\M$}}
      }
      child{node[eli]{$\ldots$}}
      child {
        node(l1b)[xor] {\LARGE +}
        child{node(l1ba)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$\M$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$y$};
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$z$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$z$};
\end{tikzpicture}
\end{center}

\section{Operator properties}

To prove Toda's theorem we need to prove the following properties:
\begin{description}
  \item[Property 1.] $\xor\xor C = \xor C$
  \item[Property 2.] $\BP\BP C = \BP C$
  \item[Property 3.] $\xor\BP C = \BP\xor C$
  \item[Property 4.] $\exists\cdot C$, $\forall \cdot C \subseteq \BP\xor C$
\end{description}

Observe that for our purposes it would suffice to prove them for $C \in
\set{\P,\xor\P, \BP\xor\P}$. Lets warm up by proving $\xor C = \xnor C$.

\subsection{$\xor C=\xnor C$}

\def\NEG{\neg\cdot}

We define the operator $\NEG$ as:

\begin{align*}
  \NEG L = \set{(x,0 y) \mid (x,y) \in L }\cup\set{(x,1)}
\end{align*}

Consider the language $\xnor \NEG L$, by unravelling the definition of
$\xnor$ we have $\xnor \NEG L = \set{x | \#(y) \st (x,y) \in \NEG L
\text{ is odd}}$. However from the definition of $\NEG$ if the number of
$y$'s such that $(x,y) \in \NEG L$ is odd then the number of $y$'s such
that $(x,y) \in L$ is even, hence $\xnor\NEG L = \xor L$. A symmetric
argument proves that $\xor \NEG L = \xnor L$.

The following diagram succintly encodes the previous argument and
demonstrates the equivalence of $\xor$ and $\xnor$.

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=1.5cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{xor}=[shape=circle,text centered, draw=black, inner sep=-1.6pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(root)[xor]{\LARGE +}
      child{node(l1a)[end]{$M(x,y)$}}
      child{node[end]{$M(x,y)$}}
      child{node[eli]{$\ldots$}}
      child{node[end]{$M(x,y)$}}
      child{node(l1b)[end]{1}};
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$y$};
\end{tikzpicture}
\end{center}

\subsection{Property 1: $\xor \xor C = \xor C$.}

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=2.4cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{xor}=[shape=circle,text centered, draw=black, inner sep=-1.6pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(root)[xor]{\LARGE +}
      child{
        node(l1a)[xor] {\LARGE +}
        child{node(l1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$\M$}}
      }
      child{node[eli]{$\ldots$}}
      child{
        node(l1b)[xor] {\LARGE +}
        child{node(l1ba)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$\M$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$y$};
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$z$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$z$};
     \begin{scope}[xshift=9cm]
  \node(xroot)[xor]{\LARGE +}
      child{node(xl1a)[end]{$\M$}}
      child{node[eli]{$\ldots$}}
      child{node(xl1b)[end]{$\M$}};
      \path (xroot) edge node[pos=.25](xl1am)[coordinate]{} (xl1a)
            (xroot) edge node[pos=.25](xl1bm)[coordinate]{} (xl1b);
      \draw[dasharrow] (xl1am) to [out=-35,in=215] (xl1bm) node[above right]{$(y,z)$};
      \end{scope}
      \path (root) edge[draw=none] node[midway]{\LARGE $\Rightarrow$} (xroot);
\end{tikzpicture}
\end{center}

This is possible since $\oplus$ is associative and for our purposes the
multiplicative increase in fan-in does not matter.

\pagebreak
\subsection{Property 2: $\BP \BP C = \BP C$.}

Let $\q$ and $\p$ be polynomials, then observe

\hskip -2cm
\begin{tikzpicture}[level/.style={sibling distance=2.4cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(root)[bag]{\textsf{BP}}
      child {
        node(l1a)[bag] {\textsf{BP}}
        child{node(l1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$\M$}}
      }
      child{
        node[eli]{$\ldots$}
      }
      child {
        node(l1b)[bag] {\textsf{BP}}
        child{node(l1ba)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$\M$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$y$};
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$z$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$z$};
      \node[left=of root,yshift=.5cm,xshift=1.5cm]{
      \begin{minipage}{2in}
      \begin{align*}
        \PR{(x,y) \in L)}&\ge 1-2^{-\q} \\
        \PR{(x,y) \in L}&\le 2^{-\q}
      \end{align*}
      \end{minipage}
      };
      \node[left=of l1a,yshift=.5cm,xshift=1.5cm]{
      \begin{minipage}{2in}
      \begin{align*}
        \PR{(x,y) \in L)}&\ge 1-2^{-\p} \\
        \PR{(x,y) \in L}&\le 2^{-\p}
      \end{align*}
      \end{minipage}
      };
     \begin{scope}[xshift=8cm]
  \node(xroot)[bag]{\textsf{BP}}
      child{node(xl1a)[end]{$\M$}}
      child{node[eli]{$\ldots$}}
      child{node(xl1b)[end]{$\M$}};
      \path (xroot) edge node[pos=.25](xl1am)[coordinate]{} (xl1a)
            (xroot) edge node[pos=.25](xl1bm)[coordinate]{} (xl1b);
      \draw[dasharrow] (xl1am) to [out=-35,in=215] (xl1bm) node[above right]{$(y,z)$};
      \node[below=of xroot,yshift=-.5cm]{
      \begin{minipage}{2in}
      \begin{align*}
        &\text{By union bound} \\
        \PR{(x,y) \in L)}&\ge 1-2^{-\p}-2^{-\q} \\
        \PR{(x,y) \in L}&\le 2^{-\p}+2^{-\q}
      \end{align*}
      \end{minipage}
      };
      \end{scope}
      \path (root) edge[draw=none] node[midway]{\LARGE $\Rightarrow$} (xroot);
\end{tikzpicture}

\subsection{Property 3: $\xor \BP C = \BP \xor C$.}

\hskip -1.3cm
\begin{tikzpicture}[level/.style={sibling distance=2.5cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{xor}=[shape=circle,text centered, draw=black, inner sep=-1.6pt]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(root)[bag]{\textsf{BP}}
      child{
        node(l1a)[xor] {\LARGE +}
        child{node(l1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$\M$}}
      }
      child{node[eli]{$\ldots$}}
      child{
        node(l1b)[xor] {\LARGE +}
        child{node(l1ba)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$\M$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$y$};
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$z$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$z$};
      \node[left=of l1am]{$N(x,y)$};

    \begin{scope}[xshift=10cm]
  \node(xroot)[xor]{\LARGE +}
      child {
        node(xl1a)[bag] {\textsf{BP}}
        child{node(xl1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(xl1ab)[end]{$\M$}}
      }
      child{node[eli]{$\ldots$}}
      child{
        node(xl1b)[bag] {\textsf{BP}}
        child{node(xl1ba)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(xl1bb)[end]{$\M$}}
      };
      \path (xroot) edge node[pos=.25](xl1am)[coordinate]{} (xl1a)
            (xroot) edge node[pos=.25](xl1bm)[coordinate]{} (xl1b)
            (xl1a) edge node[pos=.25](xl1aam)[coordinate]{} (xl1aa)
            (xl1a) edge node[pos=.25](xl1abm)[coordinate]{} (xl1ab)
            (xl1b) edge node[pos=.25](xl1bam)[coordinate]{} (xl1ba)
            (xl1b) edge node[pos=.25](xl1bbm)[coordinate]{} (xl1bb);
      \draw[dasharrow] (xl1am) to [out=-35,in=215] (xl1bm) node[right]{$z$};
      \draw[dasharrow] (xl1aam) to [out=-35,in=215] (xl1abm) node[right]{$y$};
      \draw[dasharrow] (xl1bam) to [out=-35,in=215] (xl1bbm) node[right]{$y$};
    \end{scope}
    \path (root) edge[draw=none] node[midway]{\LARGE $\Rightarrow$} (xroot);
\end{tikzpicture}
\hskip 1cm

For a fixed $x$, the probability of choosing $z$ such that $N(x,y)$ does
not work is

\[
\PR[z]{\M \neq N(x,y)} \le 2^{-\q}
\]

Hence the probability that there exists a $y$ such that $z$ does not work is

\begin{align*}
\PR[z]{\exists y \st \M \neq N(x,y)} &\le \sum_y \PR[z]{\M \neq N(x,y)} \\
&= 2^{|y|} 2^{-\q} \\
&= 2^{|y|-\q}
\end{align*}

Therefore the probability that a particular $z$ works for all choices of $y$ is

\[
\PR[z]{\forall y~\M=N(x,y)} \ge 1-2^{|y|-\q}
\]

So by choosing $\q$ sufficiently large we have $\BP\xor C = \xor \BP C$.

\subsection{Property 4: $\exists \cdot C \subseteq \BP \xor C$}

In some sense the following proof is in the same spirit of the
Razborov-Smolensky result we saw in lecture 6, since we are looking to replace
an OR gate with a XOR and a BP gate.

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=2.4cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{xor}=[shape=circle,text centered, draw=black, inner sep=-1.6pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']

  \node(xroot)[bag]{\LARGE $\vee$}
    child{node(xl1a)[end]{$\M$}}
    child{node[eli]{$\ldots$}}
    child{node(xl1b)[end]{$\M$}};
  \path (xroot) edge node[pos=.25](xl1am)[coordinate]{} (xl1a)
        (xroot) edge node[pos=.25](xl1bm)[coordinate]{} (xl1b);
  \draw[dasharrow] (xl1am) to [out=-35,in=215] (xl1bm) node[above right]{$y$};
  \begin{scope}[xshift=7cm]
  \node(root)[bag]{\textsf{BP}}
      child{
        node(l1a)[xor] {\LARGE +}
        child{node(l1aa)[end]{$\M$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$\M$}}
      }
      child{node[eli]{$\ldots$}}
      child{
        node(l1b)[xor] {\LARGE +}
        child{node(l1ba)[end]{$M'(x,y,z)$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$M'(x,y,z)$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1am) to [out=-35,in=215] (l1bm) node[right]{$z$};
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$y$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$y$};
  \end{scope}

    \path (root) edge[draw=none] node[midway]{\LARGE $\Rightarrow$} (xroot);
\end{tikzpicture}
\end{center}

For any language $L \in C$ by the argument of Valiant-Vazirani we
can construct a machine $M'$

\[
M'(x,y,z):=M(x,y) \wedge z(y)=\overline{0}
\]

such that the language $L'$ (where $L' \in C$) accepted by $M'$ satisfies the following:


\begin{align*}
  \exists y: (x,y) \in L &\iff \PR[z]{\#(y) \st (x,y,z) \in L' \text{ is even}} \ge
  \frac{1}{\p} \\
  \forall y: (x,y) \notin L &\iff \PR[z]{\#(y) \st (x,y,z) \in L' \text{ is even}}= 0
\end{align*}

Hence Valiant-Vazirani gives us what we want for $weak\textsf{-BP}$ instead of
$\textsf{BP}$. We can now use the standard amplification technique by using
$z_1,\ldots,z_k$ instead of $z$ and $y_1,\ldots,y_k$ instead of $y$.

\begin{align*}
  \exists y: (x,y) \in L \iff \PR[z_1,\ldots,z_k]{\#(y_1,\ldots,y_k) \st (x,y,z)
  \in L' \text{ is even}} &\ge 1-(1-\frac{1}{\p})^k \\
  &\ge 1-e^{-\frac{k}{\p}} \\
  &= 1-2^{-\log_2 e \frac{k}{\p}}
\end{align*}

Hence we can choose $k=\q \p/\log_2 e$ for a polynomial $\q$ to get
strong-$\textsf{BP}$. Observe that if $C$ is closed under complement then we
also get $\forall \cdot C \subseteq \BP\xor C$ from the same argument.

\section{Toda's Theorem}

\begin{theorem}[Toda's Theorem]
  $\PH \subseteq \sharpP$
\end{theorem}

\begin{proof}
  Assume $\BP \xor\P \subseteq \sharpP$ (proved in the next theorem), then to
  prove the statement it suffices to prove that $\PH \subseteq \BP\xor\P$. From
  the definition of the polynomial hierarchy we have $\PH:=\bigcup_{k \in
  \mathbb{N}} \Sigma_k^P$, we proceed by induction on $k$.

  \case{Base case.} This is trivial since by definition $\Sigma_k^P=\Pi_k^P=P$.
  \case{Inductive step.} As inductive hypothesis we assume that
  $\Sigma_k^P,\Pi_k^P \subseteq \BP\xor\P$.

  \begin{align*}
    \Sigma_k^P &\subseteq \exists\cdot\Pi_{k-1}^P & \text{by definition of the hierarchy} \\
    &\subseteq \exists\cdot\BP\xor\P &\text{by hypothesis} \\
    &\subseteq \BP\xor\BP\xor\P &\text{by property 4} \\
    &\subseteq \BP\BP\xor\xor\P &\text{by property 3} \\
    &\subseteq \BP\xor\P &\text{by property 1 and 2}
  \end{align*}
\end{proof}

\begin{theorem}
  \label{lem:ph}
  $\BP \xor\P \subseteq \sharpP$
\end{theorem}

\begin{proof}
  Suppose we had an operator $\# \cdot$ that allowed us to count the number of
  accepting paths, then clearly we could easily use such an operator to add and
  multiply the number of accepting paths.

\begin{center}
\begin{tikzpicture}[level/.style={sibling distance=2.4cm/#1}]
  \tikzstyle{bag}=[shape=circle,text centered, draw=black, inner sep=1pt]
  \tikzstyle{end}=[shape=rectangle,text centered, draw=black]
  \tikzstyle{eli}=[text centered]
  \tikzstyle{dasharrow}=[->,dashed,>=stealth']
    \node(root)[bag]{\LARGE \textasteriskcentered}
      child{
        node(l1a)[bag] {\large \#}
        child{node(l1aa)[end]{$M(x,y)$}}
        child{node[eli]{$\ldots$}}
        child{node(l1ab)[end]{$M(x,y)$}}
      }
      child{node[eli]{$\ldots$}}
      child{
        node(l1b)[bag] {\large \#}
        child{node(l1ba)[end]{$N(x,z)$}}
        child{node[eli]{$\ldots$}}
        child{node(l1bb)[end]{$N(x,z)$}}
      };
      \path (root) edge node[pos=.25](l1am)[coordinate]{} (l1a)
            (root) edge node[pos=.25](l1bm)[coordinate]{} (l1b)
            (l1a) edge node[pos=.25](l1aam)[coordinate]{} (l1aa)
            (l1a) edge node[pos=.25](l1abm)[coordinate]{} (l1ab)
            (l1b) edge node[pos=.25](l1bam)[coordinate]{} (l1ba)
            (l1b) edge node[pos=.25](l1bbm)[coordinate]{} (l1bb);
      \draw[dasharrow] (l1aam) to [out=-35,in=215] (l1abm) node[right]{$y$};
      \draw[dasharrow] (l1bam) to [out=-35,in=215] (l1bbm) node[right]{$z$};
     \begin{scope}[xshift=9cm]
  \node(xroot)[bag]{\large \#}
      child{node(xl1a)[end]{$M(x,y)\wedge N(x,z)$}}
      child{node[eli]{$\ldots$}}
      child{node(xl1b)[end]{$M(x,y)\wedge N(x,z)$}};
      \path (xroot) edge node[pos=.25](xl1am)[coordinate]{} (xl1a)
            (xroot) edge node[pos=.25](xl1bm)[coordinate]{} (xl1b);
      \draw[dasharrow] (xl1am) to [out=-35,in=215] (xl1bm) node[above right]{$(y,z)$};
      \end{scope}
      \path (root) edge[draw=none] node[midway]{\LARGE $\Rightarrow$} (xroot);
\end{tikzpicture}
\end{center}
  Hence $\#\P$ is almost a ring, except that we do not have a way to
  subtract or divide the number of accepting paths. Recalling the definition of
  $\#\P$

  \[
  f \in \#\P \iff \exists M\in \NP \st f(x)=\#(y) \st M(x,y) \text{ accepts}
  \]

  And we have that

  \begin{align*}
    f_1,f_2 \in \#\P \Rightarrow& f_1+f_2 \in \#\P \\
    &f_1 * f_2 \in \#\P
  \end{align*}

  Hence given $f \in \#\P$ we can construct any polynomial $g$ over $f$, as long
  as the degrees and coefficients are bounded by a polynomial (\ie
  $g(x)=f(x)^2+3 f(x)+2 f(x)^{10}$).

  Given a language $L \in \P$ let $L'=BP\xor L$, then by definition we have

  \begin{align*}
    x \in L' &\iff \PR[y]{\#(y) \st (x,y) \in L = 0\imod{2})} \ge 1-2^{-\q} \\
    x \notin L' &\iff \PR[y]{\#(y) \st (x,y) \in L = 1\imod{2})} \le 2^{-\q}
  \end{align*}

  Unfortunately we cannot count module 2, but what if we could construct a
  polynomial $p$ such that:

  \begin{align*}
    p(x) = 0 \imod{2^k} &\Rightarrow \#(y) \st (x,y) \in L = 0 \imod{2} \\
    p(x) = 1 \imod{2^k} &\Rightarrow \#(y) \st (x,y) \in L = 1 \imod{2}
  \end{align*}

  Assume there are $2^m$ distinct $y$'s, then we want $k$ large enough to ensure
  that for the space of $y$'s we care about $p(x) \imod 2^k = p(x)$, clearly
  $k=2m$ suffices.

  We could build such a polynomial $p$ applying $k$ times a polynomial $f$ such
  that:

  \begin{align*}
    f(x) = 0 \imod{2^{2z}} \Rightarrow x = 0 \imod{2^{z}} \\
    f(x) = 1 \imod{2^{2z}} \Rightarrow x = 1 \imod{2^{z}}
  \end{align*}

  Unfortunately a polynomial with this properties does not exist. However if we
  replace $1$ with $-1$ then there is such a polynomial, namely
  $f(x)=4x^3+3x^4$, and therefore we can construct $p$ with $f$ by a recursion
  of depth $k$.

  Therefore it follows that $L' \in \sharpP$ since we can remove the probability
  operator by just counting the number of accepting states using $p$ and
  depending if they are $\ge (1-2^{-\q})2^m$ or $\le 2^{-1} 2^m$ decide if $x
  \in L'$.

\end{proof}

\end{document}
