\documentclass[11pt, a4paper]{article}

\usepackage{../mysty}

\renewcommand{\lesson}{10}
\renewcommand{\lessontitle}{Toda's theorem}
\renewcommand{\fulltitle}{Lesson \lesson: \lessontitle}

\usepackage{xr}
\externaldocument{../lesson-09/2022b-cot-note-09}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% START DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\date{}


%\thispagestyle{empty}

\begin{center}
{\Large {\bf \fulltitle}}
\end{center}
\vspace{0.5cm}

\noindent
{\bf Theme:} Toda's theorem which states that every language in the polynomial hierarchy can be decided by a polynomial time DTM
 with oracle access to $\sharpsat$, i.e., $\pht \subseteq \pt^{\sharpsat}$.

\vspace{0.5cm}

\begin{theorem}
\label{theo:toda}
{\bf (Toda, 1991)}
$\pht\subseteq \pt^{\sharpp}$.
\end{theorem}


\section{Reduction from $\paritysat$ to $\sharpsat$} 

In the following we will use the notations from Note~11.
Recall that $\sharp \varphi$ denote the number of satisfying assignments of a (Boolean) formula $\varphi$.
For formulas $\varphi$ and $\psi$,
the formula $\varphi\sqcap\psi$ is a formula such that $\sharp(\varphi\sqcap\psi) = \sharp\varphi \cdot \sharp\psi$.

We define an operation $+$ as follows.
Let $x_1,\ldots,x_n$ and $y_1,\ldots,y_m$ be the variables in $\varphi$ and $\psi$, respectively.
Let $z$ be a new variable.
\begin{eqnarray*}
\varphi+\psi\qquad & \defeq &\qquad
\Big(\varphi \wedge z \wedge \bigwedge_{i=1}^m y_i\Big)
\qquad \vee \qquad
\Big(\psi \wedge \neg z \wedge \bigwedge_{i=1}^n x_i\Big)
\end{eqnarray*}
Note that $\sharp(\varphi+\psi) = \sharp\varphi + \sharp \psi$.





\begin{lemma}
\label{lem:paritysat-sharpsat}
There is a deterministic polynomial time algorithm $\cT$, 
that on input formula $\varphi$ and positive integer $m$ (in unary),
outputs a formula $\psi$ such that the following holds.
\begin{itemize}
\item
If $\varphi \in \paritysat$, then $\sharp\psi \equiv -1 \pmod {2^{m+1}}$.
\item
If $\varphi \notin \paritysat$, then $\sharp\psi \equiv 0 \pmod {2^{m+1}}$.
\end{itemize} 
\end{lemma}
\begin{proof}
We will use the following identity for each $i\geq 0$ and $n$.
\begin{enumerate}[(a)]
\item
If $n \equiv -1 \pmod {2^{2^i}}$,
then $4n^3 + 3n^4 \equiv -1 \pmod{ 2^{2^{i+1}}}$.
\item
If $n \equiv 0 \pmod {2^{2^i}}$,
then $4n^3 + 3n^4 \equiv 0 \pmod{ 2^{2^{i+1}}}$.
\end{enumerate}
On input $\varphi$ and $m$,
the algorithm $\cT$ does the following.
\begin{itemize}
\item
For each $i=0,1,\ldots,\lceil\log (m+1)\rceil$,
define a formula $\psi_i$ as follows.
\begin{eqnarray*}
\psi_i & \defeq & 
\left\{
\begin{array}{ll}
\varphi & \text{if}\ i =0
\\
4\psi_{i-1}^3\ + \ 3 \psi_{i-1}^4 \qquad& \text{if}\ i \geq 1
\end{array}
\right.
\end{eqnarray*}
Here $4\psi_{i-1}^3\ + \ 3\psi_{i-1}^4$ denotes the formula
that has $4\sharp(\psi_{i-1})^3 + 3\sharp(\psi_{i-1})^4$ satisfying assignments.
Such formula can be constructed using the operators $+$ and $\sqcap$.
\item
Output the formula $\psi_{\lceil\log (m+1)\rceil}$.
\end{itemize}
It is not difficult to show that the algorithm $\cT$ runs in polynomial time.
Its correctness follows directly from the identities (a) and (b).
\end{proof}


\section{Proof of Theorem~\ref{theo:toda}}

Let $L \in \pht$.
We want to show that $L \in \pt^{\sharpsat}$.
By Theorem~\ref{theo:ph-paritysat},
there is a probabilistic polynomial time algorithm $\cM_1$ that
on input $w$, outputs a formula $\psi$ such that the following holds.
\begin{itemize}
\item
If $w \in L$, then $\prarg { \psi \in \paritysat} \geq 3/4$.
\item
If $w \notin L$, then $\prarg { \psi \in \paritysat} \leq 1/4$.
\end{itemize}
Using the alternative definition of PTM, we view $\cM_1$ as a DTM
with two input $(w,r)$, where $r$ is a random string.
Let $\ell$ be the length of the random string.
Let $\cM_2$ be the algorithm
that on input $w$ and random string $r$, it outputs the formula:
$$
\cT(\cM_1(w,r),\ell+2)
$$
where $\cT$ is the algorithm in Lemma~\ref{lem:paritysat-sharpsat}.
That is, it first runs $\cM_1(w,r)$ and then runs $\cT$ on input $(\cM_1(w,r),\ell+2)$ 
Combining Theorem~\ref{theo:ph-paritysat} and Lemma~\ref{lem:paritysat-sharpsat},
on input $w$ and random string $r$, 
the algorithm $\cM_2$ outputs a formula $\psi_{w,r}$ such that the following holds.
\begin{itemize}
\item
If $w \in L$, then $\prdist {r\in \{0,1\}^{\ell}} { \sharp\psi_{w,r} \equiv -1 \pmod {2^{\ell+3}}} \geq 3/4$.
\item
If $w \notin L$, then $\prdist {r\in \{0,1\}^{\ell}} { \sharp\psi_{w,r} \equiv -1 \pmod {2^{\ell+3}}} \leq 1/4$.
\end{itemize}
This is equivalent to the following.
\begin{itemize}
\item
If $w \in L$, 
the sum $\sum_{r\in \{0,1\}^{\ell}} \sharp\psi_{w,r}$ lies in between $-2^{\ell}$ and $-\frac{3}{4}2^{\ell}$ (modulo $2^{\ell+3}$).
\item
If $w \notin L$, 
the sum $\sum_{r\in \{0,1\}^{\ell}} \sharp\psi_{w,r}$ lies in between $-\frac{1}{4}2^{\ell}$ and $0$ (modulo $2^{\ell+3}$).
\end{itemize}
The sets of values that lie in between $-2^{\ell}$ and $-\frac{3}{4}2^{\ell}$ 
and in between $-\frac{1}{4}2^{\ell}$ and $0$ (modulo $2^{\ell+3}$) are the following sets $P$ and $Q$, respectively:
\begin{eqnarray*}
P \ \defeq \
\{28\cdot 2^{\ell-2},\ldots,29\cdot2^{\ell-2}\}
& \quad\text{and}\quad &
Q \ \defeq \
\{31\cdot 2^{\ell-2},\ldots,2^{\ell+3}-1\}\ \cup\ \{0\}
\end{eqnarray*}
Note that $P$ and $Q$ are disjoint.

The main idea of Theorem~\ref{theo:toda} is that on input word $w$,
the algorithm asks the $\sharpsat$ oracle for the value $\sum_{r\in \{0,1\}^{\ell}} \sharp\psi_{w,r}$
and checks whether the value is in $P$ or $Q$.
To this end, we need to construct a formula whose number of satisfying assignments is exactly $\sum_{r\in \{0,1\}^{\ell}} \sharp\psi_{w,r}$.

Consider the following NTM $\cM'$.
On input word $w$, it does the following.
\begin{itemize}
\item
Guess a string $r\in \{0,1\}^\ell$.
\item
Run $\cM_2$ on $(w,r)$ to obtain a formula $\psi_{w,r}$.
\item
Guess a satisfying assignment for $\psi_{w,r}$.
\item
ACCEPT if and only if the guessed assignment is indeed a satisfying assignment for $\psi_{w,r}$.
\end{itemize}
Obviously, for every $w$, the number of accepting runs of $\cM'$ on $w$ is precisely $\sum_{r\in \{0,1\}^{\ell}} \sharp\psi_{w,r}$.

Now, to complete our proof, we present a polynomial time DTM $\cM$ decides $L$
(with oracle access to $\sharpsat$).
On input $w$, it does the following.
\begin{itemize}
\item
Construct a formula $\Psi_w$ such that
the number of satisfying assignments of $\Psi_w$ is exactly
the number of accepting runs of $\cM'$ on $w$.

Here we use Cook-Levin construction (on $w$ and the transitions in $\cM'$).
Recall that Cook-Levin reduction is parsimonious.
\item
Determine the value $\sharp\Psi_w$ (modulo $2^{\ell+3}$) by querying the $\sharpsat$ oracle.
\item
Determine whether $\sharp\Psi_w$ lies in $P$ or $Q$,
the answer of which implies whether $w\in L$.
\end{itemize}




\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% END OF DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%