Bit-counting complexity classes

Abstract

We define bit-counting complexity classes, where the membership depends on the binary profile of the number of accepting paths of non-deterministic polynomial time Turing machines. We study the relationship between this new family of complexity classes and the classical complexity classes. We prove that the complexity class $\mathbf{PP}$ is contained in our comparison based bit-counting complexity classes ${\mathbf{B}}_{|0|=|1|}\mathbf{P}$, ${\mathbf{B}}_{|0|<|1|}\mathbf{P}$ and ${\mathbf{B}}_{|0|>|1|}\mathbf{P}$. We further show that all of these complexity classes are Turing equivalent ${\mathbf{P}}^{\mathbf{PP}}={\mathbf{P}}^{{\mathbf{B}}_{|0|=|1|}\mathbf{P}}={\mathbf{P}}^{{\mathbf{B}}_{|0|>|1|}\mathbf{P}}={\mathbf{P}}^{{\mathbf{B}}_{|0|<|1|}\mathbf{P}}$. We also prove that complexity classes $\mathbf{NP}$ and $\mathbf{CoNP}$ are contained in both of our parity based bit-counting complexity classes ${\mathbf{B}}_{|0|\oplus }\mathbf{P}$ and ${\mathbf{B}}_{|1|\oplus }\mathbf{P}$.