Bit-counting complexity classes
For complexity theorists, this work defines a new family of classes and establishes relationships with classical classes, but the results are incremental as they do not resolve major open problems.
The paper introduces bit-counting complexity classes that depend on the binary profile of the number of accepting paths, and shows that PP is contained in the comparison-based classes, while NP and CoNP are contained in the parity-based classes. It also proves Turing equivalences among these classes and P^PP.
We define a new family of complexity classes called bit-counting complexity classes, since membership depends not merely on the number of accepting paths, but also on the binary profile of that number. We study the relationship between this new family of complexity classes and the classical complexity classes. We prove that the classical complexity class ${\bf PP}$ is contained in our comparison based bit-counting complexity classes ${\bf B_{|0|=|1|}P}$, ${\bf B_{|0|<|1|}P}$ and ${\bf B_{|0|>|1|}P}$. We further show that all of these complexity classes are Turing equivalent ${\bf P}^{\bf PP} = {\bf P}^{{\bf B_{|0|=|1|}P}}={\bf P}^{{\bf B_{|0|>|1|}P}}={\bf P}^{{\bf B_{|0|<|1|}P}}$. We also prove that classical complexity classes ${\bf NP}$ and ${\bf CoNP}$ are contained in both of our parity based bit-counting complexity classes ${\bf B_{|0| \oplus}P}$ and ${\bf B_{|1| \oplus}P}$.