Additional properties of parity based bit-counting complexity classes and hierarchies

Abstract

We study some properties of the parity based bit-counting complexity classes ${\mathbf{B}}_{|0|\oplus }\mathbf{P}$ and ${\mathbf{B}}_{|1|\oplus }\mathbf{P}$. We first prove that both of these complexity classes are closed under complement and ${\mathbf{B}}_{|1|\oplus }\mathbf{P}\subseteq {\mathbf{B}}_{|0|\oplus }\mathbf{P}$. We then prove that $\mathbf{US}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$ and $\mathbf{US}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$. We then study the class defining characteristic functions of the parity based bit-counting complexity classes, where the one associated with ${\mathbf{B}}_{|1|\oplus }\mathbf{P}$ produces the Prouhet-Thue-Morse sequence. We then prove that a contiguous block of four values from either sequence determines the parity of its starting index and use this fact to show that $\oplus \mathbf{P}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|0|\oplus }\mathbf{P}}$ and $\oplus \mathbf{P}\subseteq {\mathbf{P}}^{{\mathbf{B}}_{|1|\oplus }\mathbf{P}}$. We then use the parity based bit-counting complexity classes to define various hierarchies and show that they all contain $\mathbf{PH}$ and are contained in $\mathbf{CH}$.