Bit-counting complexity classes
2026-06-03 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors introduce new complexity classes called bit-counting complexity classes, where deciding membership depends on the pattern of zeros and ones in the binary representation of the count of accepting computation paths. They show that the well-known class PP is included in some of these new classes based on comparisons of zero and one counts. Moreover, they prove that these new classes have the same computational power as PP when used as oracles in polynomial time. Additionally, they find that NP and CoNP fit inside certain parity-based bit-counting classes. Overall, the authors explore how these novel classes relate to classical complexity classes.
Complexity classesPPNPCoNPBit-counting complexityTuring equivalencePolynomial-time oracleAccepting pathsParityBinary representation
Authors
Tayfun Pay
Abstract
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}$.