Even more properties of parity based bit-counting complexity classes

Abstract

We investigate several additional properties of parity based bit-counting complexity classes ${\mathbf{B}}_{|0|\oplus }\mathbf{P}$ and ${\mathbf{B}}_{|1|\oplus }\mathbf{P}$. We first prove that ${\mathbf{C}}_{=}\mathbf{P}=\mathbf{ES}=\mathbf{MNS}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}={\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$. We then build upon the four consecutive value theorem from \cite{P26b} and develop a bit recovery procedure that reconstructs the binary representation of a $\#P$ value one bit at a time by querying appropriately padded and shifted versions of that value. Using this procedure, we prove that $\mathbf{PP}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$ and $\mathbf{PP}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$, which consequently yields ${\mathbf{P}}^{\mathbf{PP}}={\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}={\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$. Furthermore, since this procedure recovers the complete numerical output of a $\#P$ function, it also establishes the functional containments of $\#P\subseteq {\mathbf{FP}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$ and $\#P\subseteq {\mathbf{FP}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$. We additionally demonstrate that caching repeated oracle queries reduces the number of distinct queries required for the bit recovery procedure from $4n$ to $2n+2$. Finally, we prove that parity based bit-counting hierarchies $\mathbf{\Sigma }{\mathbf{B}}_{|0|\oplus }\mathbf{H}$, $\mathbf{\Sigma }{\mathbf{B}}_{|1|\oplus }\mathbf{H}$, $\mathbf{\Delta }{\mathbf{B}}_{|0|\oplus }\mathbf{H}$ and $\mathbf{\Delta }{\mathbf{B}}_{|1|\oplus }\mathbf{H}$ contain $\mathbf{CH}$. As a result, these hierarchies coincide with $\mathbf{CH}$ since the reverse containments were already established in \cite{P26b}.