加载中…
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 is contained in our comparison based bit-counting complexity classes , and . We further show that all of these complexity classes are Turing equivalent . We also prove that complexity classes and are contained in both of our parity based bit-counting complexity classes and .

生成讲解博客的中文版本

生成AI智能校验的中文版本