Even more properties of parity based bit-counting complexity classes

Abstract

We study 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{MNS}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}={\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$ and since ${\mathbf{C}}_{=}\mathbf{P}=\mathbf{ES}=\mathbf{MNS}$ is already known, we establish 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 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}}$. We then demonstrate that the same method can be used to prove $\#P\subseteq {\mathbf{FP}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$ and $\#P\subseteq {\mathbf{FP}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$. We also show that the parity based bit-counting hierarchies contain $\mathbf{CH}$.