January 01, 1970
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 \({\boldsymbol{P}P}\) is contained in our comparison based bit-counting complexity classes \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|<|1|}P}\) and \({\boldsymbol{B}_{|0|>|1|}P}\). We further show that all of these complexity classes are Turing equivalent \({\boldsymbol{P}}^{\boldsymbol{P}P} = {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|=|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|>|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|<|1|}P}}\). We also prove that complexity classes \({\boldsymbol{N}P}\) and \({\boldsymbol{C}oNP}\) are contained in both of our parity based bit-counting complexity classes \({\boldsymbol{B}_{|0| \oplus}P}\) and \({\boldsymbol{B}_{|1| \oplus}P}\).
|tpay@gradcenter.cuny.edu|
We introduce a family of bit-counting complexity classes defined by applying predicates to the binary representation of \({\boldsymbol{\#}P}\) functions. Instead of comparing the number of accepting computation paths directly to a value, this family of complexity class examine the number of 0’s bits and 1’s bits that appear in the binary expansion of the accepting path count. Our bit-counting complexity classes provide a different perspective on counting complexity such that rather than asking whether a count is small, large, zero, odd, even or exactly equal to a threshold, they ask whether the binary description of the count satisfies some bit-counting property.
We first obtain equality among some classical complexity classes and bit-counting complexity classes purely based on definition. These are the bit-counting complexity classes that compare the count of either 0’s bits or 1’s bits to the value zero. These bit-counting complexity classes and their classical counterparts are as follows: \({\boldsymbol{B}_{|1|=0}P}={\boldsymbol{C}oNP}\), \({\boldsymbol{B}_{|1|>0}P}={\boldsymbol{N}P}\), \({\boldsymbol{B}_{|0|=0}P}={\boldsymbol{M}NS} = {\boldsymbol{C}_{=}P}\) and \({\boldsymbol{B}_{|0|>0}P}={\boldsymbol{C}oMNS} = {\boldsymbol{C}oC_{=}P}\).
We then consider comparison based bit-counting complexity classes that compare the bit count’s of 0’s bits and 1’s bits as follows: \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|>|1|}P}\) and \({\boldsymbol{B}_{|0|<|1|}P}\). We prove that the comparison based bit-counting complexity classes are strong enough to contain \({\boldsymbol{P}P}\). We show that \({\boldsymbol{P}P}\subseteq{\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{P}P}\subseteq{\boldsymbol{B}_{|0|>|1|}P}\) and \({\boldsymbol{P}P}\subseteq{\boldsymbol{B}_{|0|<|1|}P}\), using explicit \({\boldsymbol{\#}P}\) constructions that force the binary representation of the resulting count to have the desired balance between 0’s bits and 1’s bits. We also show that these comparison based bit-counting complexity classes are contained in \({\boldsymbol{P}}^{\boldsymbol{P}P}\) and that their polynomial-time Turing closures coincide with \({\boldsymbol{P}}^{\boldsymbol{P}P}\), such that \({\boldsymbol{P}}^{\boldsymbol{P}P} = {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|=|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|>|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|<|1|}P}}\).
We finally consider parity based bit-counting complexity classes as follows: \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\). We establish the bounds \({\boldsymbol{N}P}\cup{\boldsymbol{c}oNP}\subseteq{\boldsymbol{B}_{|0|\oplus}P}\), \({\boldsymbol{N}P}\cup{\boldsymbol{c}oNP}\subseteq{\boldsymbol{B}_{|1|\oplus}P}\),\({\boldsymbol{B}_{|0|\oplus}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\) and \({\boldsymbol{B}_{|0|\oplus}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). We also prove that \({\boldsymbol{B}_{|1| \oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|0| \oplus}P}}\) and \({\boldsymbol{B}_{|0| \oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|1| \oplus}P}}\), and then prove that their polynomial-time Turing closures agree, such that \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).
These results place our family of bit-counting complexity classes within the landscape of complexity hierarchy and show that predicates applied to the the binary expansion of the accepting path count can encode several classical non-deterministic and probabilistic counting phenomena.
Definition 1. A language \(L\) is in complexity class NP, if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| >0\)
Definition 2. A language \(L\) is in complexity class CoNP, if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| =0\)
Definition 3. A language \(L\) is in complexity class US, as defined in [1], if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| = 1\)
Definition 4. A language \(L\) is in complexity class \(\oplus\)P, as defined in [2], if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| \not \equiv\) 0 (Mod 2)
Definition 5. A language \(L\) is in complexity class C\(_{=}\)P, as defined in [3], if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\), \(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| = 2^{p(|x|)-1}\)
Definition 6. A language \(L\) is in complexity class ES, as defined in [4], if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| = 2^{t}\), where t \(\in \mathbb{N}_{0} = \{0,1,2, ...\}\)
Definition 7. A language \(L\) is in complexity class MNS, as defined in [5], if there exists polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| = 2^{t}-1\), where t \(\in \mathbb{N}_{>0} = \{1,2,3, ...\}\)
Definition 8. A language \(L\) is in complexity class PP, as defined in [3], if there exists a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow ||\{y| \;|y| = p(|x|) \wedge R(x, y)\}|| > 2^{p(|x|)-1}\)
Definition 9. Functional complexity class #P, as defined in [6], counts the total number of accepting paths of a non-deterministic polynomial time Turing machine.
#P = \(\{f | (\exists\) a non-deterministic polynomial time Turing machine \(M) (\forall x)\) \([f (x) = \#accept_{M}(x)]\}\).
It was shown that \({\boldsymbol{C}oNP} \subseteq {\boldsymbol{U}S} \subseteq {\boldsymbol{M}NS} = {\boldsymbol{E}S } = { \boldsymbol{C}_{=}P} \subseteq {\boldsymbol{P}P}\) and that \({\boldsymbol{P}}^{\boldsymbol{P}P} = {\boldsymbol{P}}^{{\boldsymbol{\#}P}}\). Many other complexity classes can be found in [7] and [5].
The function \(B_{0}\) counts the number of 0’s bits and the function \(B_{1}\) counts the number of 1’s bits in the binary representation of the numbers in the following definitions.
Definition 10. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0|=|1|}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(\equiv\) \(B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\)
Definition 11. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0|>|1|}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(>\) \(B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\)
Definition 12. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0|<|1|}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(<\) \(B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\)
Definition 13. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0| \oplus}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||) \not \equiv {\rm 0 (Mod 2)}\)
Definition 14. A language \(L\) is in complexity class \({\boldsymbol{B}_{|1| \oplus}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||) \not \equiv {\rm 0 (Mod 2)}\)
Definition 15. A language \(L\) is in complexity class \({\boldsymbol{B}_{|1|=0}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(= 0\)
Definition 16. A language \(L\) is in complexity class \({\boldsymbol{B}_{|1|>0}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{1}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(> 0\)
Definition 17. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0|=0}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(= 0\)
Definition 18. A language \(L\) is in complexity class \({\boldsymbol{B}_{|0|>0}P}\), if there exist a polynomial \(p\) and a polynomial-time predicate \(R\) such that, for each \(x\),
\(x \in L \Leftrightarrow B_{0}(||\{y| \;|y| = p(|x|) \wedge R(x, y)\}||)\) \(> 0\)
The following equalities follow from their respective definitions.
-\({\boldsymbol{B}_{|1|=0}P} ={\boldsymbol{C}oNP}\).
-\({\boldsymbol{B}_{|1|>0}P} ={\boldsymbol{N}P}\).
-\({\boldsymbol{B}_{|0|=0}P} = {\boldsymbol{M}NS} ={\boldsymbol{C}_{=}P}\).
-\({\boldsymbol{B}_{|0|>0}P} = {\boldsymbol{C}oMNS} = {\boldsymbol{C}oC_{=}P}\).
We establish the location of the comparison based bit-counting complexity classes \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|>|1|}P}\) and \({\boldsymbol{B}_{|0|<|1|}P}\) within the complexity hierarchy with the following seven theorems.
Theorem 1. \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|=|1|}P}\)
Proof. We use the following definition of \({\boldsymbol{B}_{|0|=|1|}P}\). A language \(L\) is in \({\boldsymbol{B}_{|0|=|1|}P}\) if there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))=B_1(H(x))\), where \(B_0(n)\) and \(B_1(n)\) denote the number of 0’s and 1’s bits, respectively, in the binary representation of \(n\).
Let \(L\in {\boldsymbol{P}P}\). Then there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomially bounded function \(m(n)\) such that, on every input \(x\) of length \(n\), the machine \(M\) uses exactly \(m(n)\) non-deterministic bits. Assume without loss of generality that \(m(n)\ge 2\) for every input length \(n\). So \(M\) has exactly \(2^{m(n)}\) computation paths on input \(x\) and \(x\in L \iff A(x)>2^{m(n)-1}\), where \(A(x)=\#\operatorname{acc}_{M}(x)\). We will use \(m=m(|x|)\) for readability. Let \(R(x)=2^m-A(x)\) be the number of rejecting paths of \(M\). The function \(R(x)\) is in \({\boldsymbol{\#}P}\), since we can construct a non-deterministic polynomial-time Turing machine that simulates \(M\) and accepts exactly on the rejecting paths of \(M\). We next define \(T=2^{m-1}\) and \(H(x)=A(x)\cdot T+R(x)+T^2-T\).
We first verify that \(H(x)\) is a valid \({\boldsymbol{\#}P}\) function. The function \(A(x)\cdot T=A(x)\cdot 2^{m-1}\) is in \({\boldsymbol{\#}P}\), since we can simulate \(M\) and, on each accepting path, guess \(m-1\) additional non-deterministic bits. The function \(R(x)\) is also in \({\boldsymbol{\#}P}\). Finally, the length-dependent term \(T^2-T=2^{2m-2}-2^{m-1}\) is a \({\boldsymbol{\#}P}\) function. To see this, construct a non-deterministic polynomial-time Turing machine that guesses a string \(y\in\{0,1\}^{2m-2}\). It rejects exactly those strings whose first \(m-1\) bits are all \(0\). There are exactly \(2^{m-1}\) such strings, since the remaining \(m-1\) bits are free. Therefore, this machine has exactly \(2^{2m-2}-2^{m-1}=T^2-T\) accepting paths. Since \({\boldsymbol{\#}P}\) is closed under addition, we have \(H(x)\in {\boldsymbol{\#}P}\).
We next prove the main theorem with the following two lemmas.
Lemma 1. If \(x\in L\), then \(B_0(H(x))=B_1(H(x))\).
Proof. Assume \(x\in L\). Since \(x\in L \iff A(x)>2^{m-1}\), we have \(A(x)>T\). So we may write \(A(x)=T+1+t\) for some integer \(t\) satisfying \(0\le t\le T-1\). Since the total number of paths is \(2^m=2T\), we have \(R(x)=2T-A(x)=2T-(T+1+t)=T-1-t\). We now compute \(H(x)=A(x)\cdot T+R(x)+T^2-T\). Substituting \(A(x)=T+1+t\) and \(R(x)=T-1-t\), we get \(H(x)=(T+1+t)T+(T-1-t)+T^2-T\). Thus, \(H(x)=2T^2+tT+(T-1-t)\).
Since \(T=2^{m-1}\), the value \(t\) can be written using exactly \(m-1\) bits. Write \(t=(b_{m-2}b_{m-3}\cdots b_0)_2\). Then \(T-1-t\) is the bitwise complement of \(t\) using exactly \(m-1\) bits. Therefore, the binary representation of \(H(x)\) is \(10\underbrace{b_{m-2}b_{m-3}\cdots b_0}_{m-1}\underbrace{\overline{b_{m-2}}\overline{b_{m-3}}\cdots \overline{b_0}}_{m-1}\).
The initial block \(10\) has one \(1\) and one \(0\). The final \(2m-2\) bits consist of \(t\) followed by its bitwise complement, so they contain exactly \(m-1\) ones and exactly \(m-1\) zeros. As a result, the full binary representation of \(H(x)\) has exactly \(m\) ones and exactly \(m\) zeros. Therefore, \(B_0(H(x))=B_1(H(x))\).\(\qed\) ◻
Lemma 2. If \(x\notin L\), then \(B_0(H(x))\neq B_1(H(x))\).
Proof. Assume \(x\notin L\). Then \(A(x)\le 2^{m-1}=T\).
First suppose \(A(x)<T\). Then \(H(x)=A(x)T+R(x)+T^2-T\). We get \(H(x)=A(x)T+(2T-A(x))+T^2-T\) since \(R(x)=2T-A(x)\) and this simplifies to \(H(x)=T^2+T+A(x)(T-1)\). Because \(0\le A(x)<T\), we have \(T^2+T\le H(x)<2T^2\). Since \(T=2^{m-1}\), this means that \(2^{2m-2}<H(x)<2^{2m-1}\). As a result, the binary representation of \(H(x)\) has exactly \(2m-1\) bits. Consequently, it cannot have the same number of 0’s and 1’s bits since \(2m-1\) is odd. As a result, \(B_0(H(x))\neq B_1(H(x))\).
Next suppose \(A(x)=T\). Then \(R(x)=T\) and \(H(x)=T\cdot T+T+T^2-T=2T^2\). Since \(T=2^{m-1}\), we have \(H(x)=2^{2m-1}\). The binary representation of \(2^{2m-1}\) is a single \(1\) followed by \(2m-1\) zeros, which means that \(B_1(H(x))=1\) and \(B_0(H(x))=2m-1\). We have \(2m-1\neq 1\) since we already assumed that \(m\ge 2\). As a result, \(B_0(H(x))\neq B_1(H(x))\). Therefore, if \(x\notin L\), then \(B_0(H(x))\neq B_1(H(x))\).\(\qed\) ◻
The two lemmas show that \(x\in L \iff B_0(H(x))=B_1(H(x))\). Since \(H(x)\in {\boldsymbol{\#}P}\), we have that \(L\in {\boldsymbol{B}_{|0|=|1|}P}\). Since \(L\in{\boldsymbol{P}P}\) was any \(L\), then we can conclude that \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|=|1|}P}\).\(\qed\) ◻
Theorem 2. \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|>|1|}P}\)
Proof. We use the following definition of \({\boldsymbol{B}_{|0|>|1|}P}\). A language \(L\) is in \({\boldsymbol{B}_{|0|>|1|}P}\) if there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))>B_1(H(x))\), where \(B_0(n)\) and \(B_1(n)\) denote the number of 0’s and 1’s bits, respectively, in the binary representation of \(n\).
Let \(L\in {\boldsymbol{P}P}\). Then there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomially bounded function \(m(n)\) such that, on every input \(x\) of length \(n\), the machine \(M\) uses exactly \(m(n)\) non-deterministic bits. Assume without loss of generality that \(m(n)\ge 2\) for every input length \(n\). So \(M\) has exactly \(2^{m(n)}\) computation paths on input \(x\) and \(x\in L \iff A(x)>2^{m(n)-1}\), where \(A(x)=\#\operatorname{acc}_{M}(x)\). We will use \(m=m(|x|)\) for readability. We define \(T=2^{m-1}\), \(\ell=2m+1\) and \(H(x)=A(x)+2^\ell-T-1\).
We first verify that \(H(x)\) is a valid \(\#P\) function. The function \(A(x)\) is in \({\boldsymbol{\#}P}\) by definition. Also, the length-dependent term \(2^\ell-T-1=2^\ell-2^{m-1}-1\) is a \({\boldsymbol{\#}P}\) function. To see this, construct a non-deterministic polynomial-time Turing machine that guesses a string \(y\in\{0,1\}^{\ell}\). It rejects exactly those strings whose first \(\ell-(m-1)=\ell-m+1\) bits are all \(0\) and it also rejects one additional string, say \(10\cdots 0\). These two rejection conditions are disjoint. The first condition rejects exactly \(2^{m-1}\) strings, since the remaining \(m-1\) bits are free and the second condition rejects exactly one additional string. Therefore, this machine has exactly \(2^\ell-2^{m-1}-1\) accepting paths. Since \({\boldsymbol{\#}P}\) is closed under addition, we have \(H(x)=A(x)+2^\ell-2^{m-1}-1\in {\boldsymbol{\#}P}\).
We now prove the main theorem with the following two lemmas.
Lemma 3. If \(x\in L\), then \(B_0(H(x))>B_1(H(x))\).
Proof. Assume \(x\in L\). Since \(x\in L \iff A(x)>2^{m-1}\), we have \(A(x)>T\). So we may write \(A(x)=T+s\) for some integer \(s\ge 1\). Since \(A(x)\le 2^m\), we also have \(s\le 2^m-T=T=2^{m-1}\). Now \(H(x)=A(x)+2^\ell-T-1=(T+s)+2^\ell-T-1=2^\ell+(s-1)\). Let \(t=s-1\). Then \(0\le t\le 2^{m-1}-1\). Writing \(t\) in binary using exactly \(m-1\) bits as \(t=(b_{m-2}b_{m-3}\cdots b_0)_2\), the binary representation of \(H(x)=2^\ell+t\) is \(1\underbrace{00\cdots 0}_{\ell-m+1}\underbrace{b_{m-2}b_{m-3}\cdots b_0}_{m-1}\).
Thus, the binary representation of \(H(x)\) has a leading \(1\) in the \(2^\ell\) position, followed by \(\ell-m+1\) forced zeros, followed by the \(m-1\) lower-order bits encoding \(t\). The lower-order part contributes at most \(m-1\) ones. When we also include the leading \(1\), we get at most \(1+(m-1)=m\) ones. Thus, \(B_1(H(x))\le 1+(m-1)=m\). Also, the forced middle block contributes exactly \(\ell-m+1\) zeros. So then we get at least \(\ell-m+1=(2m+1)-m+1=m+2\) zeros, since \(\ell=2m+1\). Thus, \(B_0(H(x))\ge m+2\). As a result, we get \(B_1(H(x))\le m<m+2\le B_0(H(x))\). Therefore, \(B_0(H(x))>B_1(H(x))\).\(\qed\) ◻
Lemma 4. If \(x\notin L\), then \(B_0(H(x)) < B_1(H(x))\).
Proof. Assume \(x\notin L\). Then \(A(x)\le 2^{m-1}=T\). Therefore, \(0\le A(x)\le T\). We have \(2^\ell-T-1\le H(x)\le 2^\ell-1\) since \(H(x)=2^\ell-T-1+A(x)\). This becomes \(2^\ell-2^{m-1}-1\le H(x)\le 2^\ell-1\), since \(T=2^{m-1}\). Note that the lower endpoint \(2^\ell-2^{m-1}-1\) has binary representation \(\underbrace{11\cdots 1}_{\ell-m}0\underbrace{11\cdots 1}_{m-1}\), while the upper endpoint \(2^\ell-1\) has binary representation \(\underbrace{11\cdots 1}_{\ell}\). As a result, every number in the interval \([2^\ell-2^{m-1}-1,\,2^\ell-1]\) has binary length exactly \(\ell\) and begins with at least \(\ell-m\) consecutive \(1\)’s. The remaining \(m\) lower-order bits may vary, and they may contain several \(0\)’s bits, one \(0\) bit, or no \(0\)’s bits. Thus, \(B_1(H(x))\ge \ell-m\). We have \(\ell-m=(2m+1)-m=m+1\), since \(\ell=2m+1\). So then we have \(B_1(H(x))\ge m+1\). Also, since the binary representation of \(H(x)\) has exactly \(\ell=2m+1\) bits, the number of zero bits is at most \((2m+1)-(m+1)=m\). Thus, \(B_0(H(x))\le m\). As a result, we get \(B_0(H(x))\le m<m+1\le B_1(H(x))\). Therefore, \(B_0(H(x))< B_1(H(x))\).\(\qed\) ◻
The two lemmas show that \(x\in L \iff B_0(H(x))>B_1(H(x))\). Since \(H(x)\in {\boldsymbol{\#}P}\), we have that \(L\in {\boldsymbol{B}_{|0|>|1|}P}\). Since \(L\in{\boldsymbol{P}P}\) was any \(L\), then we can conclude that \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|>|1|}P}\).\(\qed\) ◻
Theorem 3. \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|<|1|}P}\)
Proof. We use the following definition of \({\boldsymbol{B}_{|0|<|1|}P}\). A language \(L\) is in \({\boldsymbol{B}_{|0|<|1|}P}\) if there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_1(H(x))>B_0(H(x))\), where \(B_1(n)\) and \(B_0(n)\) denote the number of 1’s and 0’s bits, respectively, in the binary representation of \(n\).
Let \(L\in {\boldsymbol{P}P}\). Then there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomially bounded function \(m(n)\) such that, on every input \(x\) of length \(n\), the machine \(M\) uses exactly \(m(n)\) non-deterministic bits. Assume without loss of generality that \(m(n)\ge 2\) for every input length \(n\). So \(M\) has exactly \(2^{m(n)}\) computation paths on input \(x\) and \(x\in L \iff A(x)>2^{m(n)-1}\), where \(A(x)=\#\operatorname{acc}_{M}(x)\). We will use \(m=m(|x|)\) for readability. Let \(R(x)=2^m-A(x)\) be the number of rejecting paths of \(M\). The function \(R(x)\) is in \({\boldsymbol{\#}P}\), since we can construct a non-deterministic Turing machine that simulates \(M\) and accepts exactly on the rejecting paths of \(M\). We next define \(T=2^{m-1}\), \(\ell=2m+1\) and \(H(x) = R(x)+2^\ell-T\).
We first verify that \(H(x)\) is a valid \(\#P\) function. The function \(R(x)\) is in \({\boldsymbol{\#}P}\). Also, the length dependent term \(2^\ell-T = 2^\ell-2^{m-1}\) is a \({\boldsymbol{\#}P}\) function. To see this, construct a non-deterministic polynomial-time Turing machine that guesses a string \(y\in\{0,1\}^{\ell}\). It rejects exactly those strings whose first \(\ell-(m-1)=\ell-m+1\) bits are all \(0\). There are exactly \(2^{m-1}\) such strings, since the remaining \(m-1\) bits are free. Therefore, this machine has exactly \(2^\ell-2^{m-1}\) accepting paths. Since \({\boldsymbol{\#}P}\) is closed under addition, we have \(H(x)=R(x)+2^\ell-2^{m-1}\in {\boldsymbol{\#}P}\).
We now prove the main theorem with the following two lemmas.
Lemma 5. If \(x\in L\), then \(B_1(H(x))>B_0(H(x))\).
Proof. Assume \(x\in L\). Since \(x\in L \iff A(x)>2^{m-1}\), we have \(A(x)>T\). Therefore, \(R(x)=2^m-A(x)<2^m-T=T\). So \(0\le R(x)\le T-1\). Thus, \(H(x)=2^\ell-T+R(x)\) lies in the interval \(2^\ell-T \le H(x) \le 2^\ell-1\). Since \(T=2^{m-1}\), the lower endpoint is \(2^\ell-2^{m-1}\). Its binary representation is \(\underbrace{11\cdots 1}_{\ell-m+1} \underbrace{00\cdots 0}_{m-1}\).
Every number in the interval \([2^\ell-2^{m-1},\,2^\ell-1]\) has at least the first \(\ell-m+1\) bits equal to \(1\). Thus, \(B_1(H(x))\ge \ell-m+1\). We get \(\ell-m+1=(2m+1)-m+1=m+2\), since \(\ell=2m+1\). Thus, \(B_1(H(x))\ge m+2\). All possible zeros occur only among the final \(m-1\) lower-order positions. Thus, \(B_0(H(x))\le m-1\). As a result, we get \(B_0(H(x))\le m-1 < m+2 \le B_1(H(x))\). Therefore, \(B_1(H(x))>B_0(H(x))\).\(\qed\) ◻
Lemma 6. If \(x\notin L\), then \(B_1(H(x)) < B_0(H(x))\).
Proof. Assume \(x\notin L\). Then \(A(x)\le 2^{m-1}=T\). Therefore, \(R(x)=2^m-A(x)\ge 2^m-T=T\). So we may write \(R(x)=T+s\) for some integer \(s\ge 0\). Since \(R(x)\le 2^m\), we also have \(s\le 2^m-T=T=2^{m-1}\). Now \(H(x) = R(x)+2^\ell-T = (T+s)+2^\ell-T = 2^\ell+s\). Writing \(s\) in binary using exactly \(m\) bits as \(s=(b_{m-1}b_{m-2}\cdots b_0)_2\), the binary representation of \(H(x)=2^\ell+s\) is \(1\underbrace{00\cdots 0}_{\ell-m}\underbrace{b_{m-1}b_{m-2}\cdots b_0}_{m}\).
Thus, the binary representation of \(H(x)\) has a leading \(1\) in the \(2^\ell\) position, followed by \(\ell-m\) forced zeros, followed by the \(m\) lower-order bits encoding \(s\). Since \(0\le s\le 2^{m-1}\), the lower-order part contributes at most \(m-1\) ones. As a result, \(B_1(H(x))\le 1+(m-1)=m\). The binary length of \(H(x)\) is \(\ell+1\). Thus, \(B_0(H(x)) = (\ell+1)-B_1(H(x))\). Using \(B_1(H(x))\le m\), we obtain \(B_0(H(x)) \ge (\ell+1)-m\). We get \(B_0(H(x)) \ge (2m+2)-m = m+2\) since \(\ell=2m+1\). As a result, we get \(B_1(H(x))\le m < m+2 \le B_0(H(x))\). Therefore, \(B_1(H(x))<B_0(H(x))\). \(\qed\) ◻
The two lemmas show that \(x\in L \iff B_1(H(x))>B_0(H(x))\). Since \(H(x)\in {\boldsymbol{\#}P}\), we have that \(L\in {\boldsymbol{B}_{|0|<|1|}P}\). Since \(L\in{\boldsymbol{P}P}\) was any \(L\), then we can conclude that \({\boldsymbol{P}P}\subseteq {\boldsymbol{B}_{|0|<|1|}P}\). \(\qed\) ◻
Theorem 4. \({\boldsymbol{B}_{|0|=|1|}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. Let \(L\in{\boldsymbol{B}_{|0|=|1|}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))=B_1(H(x))\), where \(B_0(n)\) and \(B_1(n)\) denote the number of \(0\)’s and \(1\)’s bits, respectively, in the standard binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
We claim that a \({\boldsymbol{P}}^{\boldsymbol{P}P}\) machine can recover the exact value of \(H(x)\). We can observe this by considering threshold questions of the form \(H(x)\ge z\), where \(1\le z\le 2^q\). Each such threshold question is in \({\boldsymbol{P}P}\). To see this, construct an auxiliary non-deterministic machine with exactly \(2^{q+1}\) computation paths as follows: One half of the paths simulate \(M(x)\) and contribute exactly \(H(x)\) accepting paths, while the other half accepts exactly \(2^q-z+1\) paths. Therefore, the auxiliary machine has exactly \(H(x)+(2^q-z+1)\) accepting paths. Its majority threshold is \(2^q\), and \(H(x)+(2^q-z+1)>2^q\) if and only if \(H(x)\ge z\). Thus, the threshold language \(\{(x,z):H(x)\ge z\}\) is in \({\boldsymbol{P}P}\).
Using this \({\boldsymbol{P}P}\) oracle, a deterministic polynomial-time machine can recover \(H(x)\) by binary search over the interval \(0\le H(x)\le 2^{q}\). Once it has recovered \(H(x)\), it can write down the binary representation of \(H(x)\), compute \(B_0(H(x))\) and \(B_1(H(x))\) and accept exactly when \(B_0(H(x))=B_1(H(x))\). Therefore, \(L\in{\boldsymbol{P}}^{\boldsymbol{P}P}\). Since \(L\in{\boldsymbol{B}_{|0|=|1|}P}\) was any \(L\), then we can conclude that \({\boldsymbol{B}_{|0|=|1|}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). \(\qed\) ◻
Theorem 5. \({\boldsymbol{B}_{|0|>|1|}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. Let \(L\in{\boldsymbol{B}_{|0|>|1|}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))>B_1(H(x))\), where \(B_0(n)\) and \(B_1(n)\) denote the number of \(0\)’s and \(1\)’s bits, respectively, in the standard binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
As shown in the previous theorem, threshold questions of the form \(H(x)\ge z\), where \(1\le z\le 2^q\), are in \({\boldsymbol{P}P}\). Therefore, a deterministic polynomial-time machine with access to a \({\boldsymbol{P}P}\) oracle can recover the exact value of \(H(x)\) by binary search over the interval \(0\le H(x)\le 2^q\). After recovering \(H(x)\), the machine computes its standard binary representation, counts the number of \(0\)’s and \(1\)’s bits, and accepts exactly when \(B_0(H(x))>B_1(H(x))\). Therefore, \(L\in{\boldsymbol{P}}^{\boldsymbol{P}P}\). Since \(L\in{\boldsymbol{B}_{|0|>|1|}P}\) was any \(L\), then we can conclude that \({\boldsymbol{B}_{|0|>|1|}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\).\(\qed\) ◻
Theorem 6. \({\boldsymbol{B}_{|0|<|1|}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. Let \(L\in{\boldsymbol{B}_{|0|<|1|}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))<B_1(H(x))\), where \(B_0(n)\) and \(B_1(n)\) denote the number of \(0\)’s and \(1\)’s bits, respectively, in the standard binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
As shown in previous theorems, threshold questions of the form \(H(x)\ge z\), where \(1\le z\le 2^q\), are in \({\boldsymbol{P}P}\). Therefore, a deterministic polynomial-time machine with access to a \({\boldsymbol{P}P}\) oracle can recover the exact value of \(H(x)\) by binary search over the interval \(0\le H(x)\le 2^q\). After recovering \(H(x)\), the machine computes its standard binary representation, counts the number of 1’s and 0’s bits and accepts exactly when \(B_0(H(x))<B_1(H(x))\). Therefore, \(L\in{\boldsymbol{P}}^{\boldsymbol{P}P}\). Since \(L\in{\boldsymbol{B}_{|0|<|1|}P}\) was any \(L\), then we can conclude that \({\boldsymbol{B}_{|0|<|1|}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\).\(\qed\) ◻
Theorem 7. \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|=|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|>|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|<|1|}P}}={\boldsymbol{P}}^{\boldsymbol{P}P}\).
Proof. Let \(\mathcal{C}\) be any one of the following three classes:
\(\mathcal{C}\in\{{\boldsymbol{B}_{|0|=|1|}P},{\boldsymbol{B}_{|0|>|1|}P},{\boldsymbol{B}_{|0|<|1|}P}\}\).
From the previous containment theorems, we have \(\mathcal{C}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). Also, from the earlier theorems, we have \({\boldsymbol{P}P}\subseteq\mathcal{C}\). We now show that \({\boldsymbol{P}}^{\mathcal{C}}={\boldsymbol{P}}^{\boldsymbol{P}P}\).
First, since \({\boldsymbol{P}P}\subseteq\mathcal{C}\), any \({\boldsymbol{P}}^{\boldsymbol{P}P}\) computation can be simulated by a \({\boldsymbol{P}}^{\mathcal{C}}\) computation. Therefore, \({\boldsymbol{P}}^{\boldsymbol{P}P}\subseteq{\boldsymbol{P}}^{\mathcal{C}}\). Second, since \(\mathcal{C}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\), any oracle query to a language in \(\mathcal{C}\) can be simulated by a deterministic polynomial-time computation with access to a \({\boldsymbol{P}P}\) oracle. Therefore, \({\boldsymbol{P}}^{\mathcal{C}}\subseteq{\boldsymbol{P}}^{{\boldsymbol{P}}^{\boldsymbol{P}P}}\). However, nested deterministic polynomial-time oracle computations collapse, so \({\boldsymbol{P}}^{{\boldsymbol{P}}^{\boldsymbol{P}P}}={\boldsymbol{P}}^{\boldsymbol{P}P}\). Thus, \({\boldsymbol{P}}^{\mathcal{C}}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). Combining the two containments gives \({\boldsymbol{P}}^{\mathcal{C}}={\boldsymbol{P}}^{\boldsymbol{P}P}\).
Since \(\mathcal{C}\) was any one of \(\{{\boldsymbol{B}_{|0|=|1|}P},{\boldsymbol{B}_{|0|>|1|}P},{\boldsymbol{B}_{|0|<|1|}P}\}\), then we can conclude that \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|=|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|>|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|<|1|}P}}={\boldsymbol{P}}^{\boldsymbol{P}P}\).\(\qed\) ◻
We establish the location of the parity based bit-counting complexity classes \({\boldsymbol{B}_{|0| \oplus}P}\) and \({\boldsymbol{B}_{|1| \oplus}P}\) within the complexity hierarchy with the following ten theorems.
Theorem 8. \({\boldsymbol{N}P}\subseteq {\boldsymbol{B}_{|1| \oplus}P}\)
Proof. We use the following definition of \({\boldsymbol{B}_{|1| \oplus}P}\). A language \(L\) is in \({\boldsymbol{B}_{|1| \oplus}P}\) if there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_1(H(x))\not\equiv 0 \pmod 2\), where \(B_1(n)\) denotes the number of \(1\)’s bits in the binary representation of \(n\). Let \(L\in{\boldsymbol{N}P}\). Then there is a polynomial-time predicate \(R\) and a polynomial \(p\) such that, for every input \(x\), \(x\in L \iff \exists y \text{ such that } |y|=p(|x|) \text{ and } R(x,y)\). Define \(f(x)=||\{y \mid |y|=p(|x|) \wedge R(x,y)\}||\). Then \(f(x)\) is a \({\boldsymbol{\#}P}\) function and \(x\in L \iff f(x)>0\). We will write \(p=p(|x|)\) for readability. We define \(r=2p+1\), which is odd. We also have \(f(x)<2^r\), since \(f(x)\le 2^p\) and \(p<r\). We next define \(H(x)=(2^r-1)f(x)\).
We first verify that \(H(x)\) is a valid \({\boldsymbol{\#}P}\) function. Construct a non-deterministic polynomial-time Turing machine as follows. On input \(x\), it first guesses a string \(y\in\{0,1\}^{p}\). If \(R(x,y)\) is false, it rejects. If \(R(x,y)\) is true, it guesses another string \(z\in\{0,1\}^{r}\) and accepts if and only if \(z\neq 00\cdots 0\). For each accepting witness \(y\), there are exactly \(2^r-1\) accepting choices of \(z\). Therefore, the total number of accepting paths is exactly \((2^r-1)f(x)\). So \(H(x)\in{\boldsymbol{\#}P}\).
We next prove the main theorem with the following two lemmas.
Lemma 7. If \(x\notin L\), then \(B_1(H(x))\equiv 0 \pmod 2\).
Proof. Suppose \(x\notin L\). Then \(f(x)=0\) and \(H(x)=0\). The binary representation of \(0\) is \(0\), so \(B_1(H(x))=0\). Therefore, \(B_1(H(x))\equiv 0 \pmod 2\).\(\qed\) ◻
Lemma 8. If \(x\in L\), then \(B_1(H(x))\not\equiv 0 \pmod 2\).
Proof. Suppose \(x\in L\). Then \(f(x)>0\), so \(1\le f(x)<2^r\). We can rewrite \(H(x)\) as \(H(x)=f(x)2^r-f(x)=(f(x)-1)2^r+(2^r-f(x))\). We can then write \(f(x)-1\) as an \(r\)-bit string \(a_{r-1}a_{r-2}\cdots a_0\), because \(0\le f(x)-1<2^r\). Also, \(2^r-f(x)=2^r-1-(f(x)-1)\), so the \(r\)-bit string for \(2^r-f(x)\) is the bitwise complement \(\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0\), where \(\overline{a}_i=1-a_i\). Therefore, \(H(x)\) is represented by the two consecutive \(r\)-bit blocks \(\underbrace{a_{r-1}a_{r-2}\cdots a_0}_{f(x)-1}\underbrace{\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0}_{2^r-f(x)}\).
Note that the term \((f(x)-1)2^r\) shifts the first block \(r\) positions to the left, and the term \(2^r-f(x)\) occupies the lower \(r\) positions. For each \(i\), exactly one of \(a_i\) and \(\overline{a}_i\) is equal to \(1\). So the two blocks contain exactly \(r\) many \(1\)’s altogether. Thus \(B_1(H(x))=r\), which is odd since \(r=2p+1\). Therefore, \(B_1(H(x))\not\equiv 0 \pmod 2\).\(\qed\) ◻
By the two lemmas, \(x\in L \iff B_1(H(x))\not\equiv 0 \pmod 2\). Therefore, \(L\in{\boldsymbol{B}_{|1| \oplus}P}\). Since \(L\in{\boldsymbol{N}P}\) was any \(L\), then we can conclude that \({\boldsymbol{N}P}\subseteq {\boldsymbol{B}_{|1| \oplus}P}\).\(\qed\) ◻
Theorem 9. \({\boldsymbol{N}P}\subseteq {\boldsymbol{B}_{|0| \oplus}P}\)
Proof. We use the following definition of \({\boldsymbol{B}_{|0| \oplus}P}\). A language \(L\) is in \({\boldsymbol{B}_{|0| \oplus}P}\) if there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))\not\equiv 0 \pmod 2\), where \(B_0(n)\) denotes the number of \(0\)’s bits in the binary representation of \(n\). Let \(L\in{\boldsymbol{N}P}\). Then there is a polynomial-time predicate \(R\) and a polynomial \(p\) such that, for every input \(x\), \(x\in L \iff \exists y \text{ such that } |y|=p(|x|) \text{ and } R(x,y)\). Define \(f(x)=||\{y \mid |y|=p(|x|) \wedge R(x,y)\}||\). Then \(f(x)\) is a \({\boldsymbol{\#}P}\) function and \(x\in L \iff f(x)>0\). We will use \(p=p(|x|)\) for readability. We define \(r=2p+1\) and \(\ell=2r\). Then \(r\) is odd and \(\ell\) is even. We also have \((2^r-1)f(x)<2^{r+p}<2^\ell\) since \(f(x)\le2^p\). We next define \(H(x)=2^\ell+(2^r-1)f(x)\).
We first verify that \(H(x)\) is a valid \({\boldsymbol{\#}P}\) function. The term \(2^\ell\) is a \({\boldsymbol{\#}P}\) function, because a non-deterministic polynomial-time Turing machine can guess a string of length \(\ell\) and accept on every branch. The term \((2^r-1)f(x)\) is also a \({\boldsymbol{\#}P}\) function such that on input \(x\), guess a string \(y\in\{0,1\}^{p}\). If \(R(x,y)\) is false, reject. If \(R(x,y)\) is true, guess a string \(z\in\{0,1\}^{r}\) and accept if and only if \(z\neq 00\cdots 0\). For each accepting witness \(y\), there are exactly \(2^r-1\) accepting choices of \(z\), so the total number of accepting paths is \((2^r-1)f(x)\). Since \({\boldsymbol{\#}P}\) is closed under addition, we have \(H(x)=2^\ell+(2^r-1)f(x)\in{\boldsymbol{\#}P}\).
We next prove the main theorem with the following two lemmas.
Lemma 9. If \(x\notin L\), then \(B_0(H(x))\equiv 0 \pmod 2\).
Proof. Suppose \(x\notin L\). Then \(f(x)=0\) and \(H(x)=2^\ell\). The binary representation of \(2^\ell\) is a single \(1\) followed by \(\ell\) many \(0\)’s. Thus, \(B_0(H(x))=\ell\), which is even since \(\ell=2r=4p+2\). Therefore, \(B_0(H(x))\equiv 0 \pmod 2\).\(\qed\) ◻
Lemma 10. If \(x\in L\), then \(B_0(H(x))\not\equiv 0 \pmod 2\).
Proof. Suppose \(x\in L\). Then \(f(x)>0\), so \(1\le f(x)<2^r\). Let \(K=(2^r-1)f(x)\), so that \(H(x)=2^\ell+K\). We first show that \(K\) has exactly \(r\) many \(1\)’s in its binary representation. We can rewrite \(K\) as \(K=(2^r-1)f(x)=f(x)2^r-f(x)=(f(x)-1)2^r+(2^r-f(x))\). We can then write \(f(x)-1\) as an \(r\)-bit string \(a_{r-1}a_{r-2}\cdots a_0\), because \(0\le f(x)-1<2^r\). Also, \(2^r-f(x)=2^r-1-(f(x)-1)\), so the \(r\)-bit string for \(2^r-f(x)\) is the bitwise complement \(\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0\), where \(\overline{a}_i=1-a_i\). Therefore, \(K\) is represented by the two consecutive \(r\)-bit blocks \(\underbrace{a_{r-1}a_{r-2}\cdots a_0}_{f(x)-1}\underbrace{\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0}_{2^r-f(x)}\).
Note that the term \((f(x)-1)2^r\) shifts the first block \(r\) positions to the left, and the term \(2^r-f(x)\) occupies the lower \(r\) positions. For each \(i\), exactly one of \(a_i\) and \(\overline{a}_i\) is equal to \(1\). So the two blocks contain exactly \(r\) many \(1\)’s altogether. Thus \(K\) has exactly \(r\) many \(1\)’s in its binary representation. Since \(K<2^\ell\), the binary representation of \(H(x)=2^\ell+K\) has a leading \(1\) in position \(\ell\), followed by the actual lower-order bit positions \(0,1,\dots,\ell-1\). These lower \(\ell\) positions contain exactly the bits of \(K\) in their corresponding positions, and every lower position not occupied by a \(1\) is a genuine \(0\)-bit of \(H(x)\). Since exactly \(r\) of these lower positions are \(1\)’s, the remaining \(\ell-r\) lower positions are \(0\)’s. Thus \(B_0(H(x))=\ell-r=(4p+2)-(2p+1)=2p+1\), which is odd. Therefore, \(B_0(H(x))\not\equiv 0 \pmod 2\).\(\qed\) ◻
By the two lemmas, \(x\in L \iff B_0(H(x))\not\equiv 0 \pmod 2\). Therefore, \(L\in{\boldsymbol{B}_{|0| \oplus}P}\). Since \(L\in{\boldsymbol{N}P}\) was for any \(L\), then we can conclude that \({\boldsymbol{N}P}\subseteq {\boldsymbol{B}_{|0| \oplus}P}\).\(\qed\) ◻
Theorem 10. \({\boldsymbol{c}oNP}\subseteq {\boldsymbol{B}_{|1|\oplus}P}\)
Proof. Let \(L\in{\boldsymbol{c}oNP}\). Then there is a polynomial-time predicate \(R\) and a polynomial \(p\) such that, for every input \(x\), \(x\in L \iff \nexists y \text{ such that } |y|=p(|x|) \text{ and } R(x,y)\). Define \(f(x)=||\{y\mid |y|=p(|x|)\wedge R(x,y)\}||\). Then \(f(x)\) is a \({\boldsymbol{\#}P}\) function and \(x\in L \iff f(x)=0\). We will use \(p=p(|x|)\) for readability. We define \(r=2p+1\) and \(\ell=4p+3\). Then both \(r\) and \(\ell\) are odd. We have \((2^r-1)f(x)<2^{r+p}<2^\ell\), since \(f(x)\le 2^p\). We next define \(H(x)=2^\ell+(2^r-1)f(x)\).
We first verify that \(H(x)\) is a valid \({\boldsymbol{\#}P}\) function. The term \(2^\ell\) is a \({\boldsymbol{\#}P}\) function, since a non-deterministic polynomial-time Turing machine can guess a string of length \(\ell\) and accept on every branch. The term \((2^r-1)f(x)\) is also a \({\boldsymbol{\#}P}\) function such that for each witness \(y\) counted by \(f(x)\), guess a string \(z\in\{0,1\}^r\) and accept if and only if \(z\neq 00\cdots 0\). This gives exactly \(2^r-1\) accepting paths for each such \(y\). Since \({\boldsymbol{\#}P}\) is closed under addition, \(H(x)\in{\boldsymbol{\#}P}\).
We next prove the main theorem with the following two lemmas.
Lemma 11. If \(x\in L\), then \(B_1(H(x))\not\equiv 0 \pmod 2\).
Proof. Suppose \(x\in L\). Then \(f(x)=0\) and \(H(x)=2^\ell\). The binary representation of \(2^\ell\) is a single \(1\) followed by \(\ell\) many \(0\)’s. Thus \(B_1(H(x))=1\), which is odd. Therefore, \(B_1(H(x))\not\equiv 0 \pmod 2\).\(\qed\) ◻
Lemma 12. If \(x\notin L\), then \(B_1(H(x))\equiv 0 \pmod 2\).
Proof. Suppose \(x\notin L\). Then \(f(x)>0\), so \(1\le f(x)<2^r\). Let \(K=(2^r-1)f(x)\), so that \(H(x)=2^\ell+K\). We first show that \(K\) has exactly \(r\) many \(1\)’s in its binary representation. We can rewrite \(K\) as \(K=(2^r-1)f(x)=f(x)2^r-f(x)=(f(x)-1)2^r+(2^r-f(x))\). We can then write \(f(x)-1\) as an \(r\)-bit string \(a_{r-1}a_{r-2}\cdots a_0\), because \(0\le f(x)-1<2^r\). Also, \(2^r-f(x)=2^r-1-(f(x)-1)\), so the \(r\)-bit string for \(2^r-f(x)\) is the bitwise complement \(\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0\), where \(\overline{a}_i=1-a_i\). Therefore, \(K\) is represented by the two consecutive \(r\)-bit blocks \(\underbrace{a_{r-1}a_{r-2}\cdots a_0}_{f(x)-1}\underbrace{\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0}_{2^r-f(x)}\).
Note that the term \((f(x)-1)2^r\) shifts the first block \(r\) positions to the left, and the term \(2^r-f(x)\) occupies the lower \(r\) positions. For each \(i\), exactly one of \(a_i\) and \(\overline{a}_i\) is equal to \(1\). So the two blocks contain exactly \(r\) many \(1\)’s altogether. Thus \(K\) has exactly \(r\) many \(1\)’s in its binary representation. Since \(K<2^\ell\), adding \(2^\ell\) creates one new leading \(1\) and does not interfere with the lower-order bits. Thus, \(B_1(H(x))=1+r\) is even, since \(r=2p+1\) is odd. Therefore, \(B_1(H(x))\equiv 0 \pmod 2\).\(\qed\) ◻
By the two lemmas, \(x\in L \iff B_1(H(x))\not\equiv 0 \pmod 2\). Therefore, \(L\in{\boldsymbol{B}_{|1|\oplus}P}\). Since \(L\in{\boldsymbol{c}oNP}\) was any \(L\), then we can conclude that \({\boldsymbol{c}oNP}\subseteq {\boldsymbol{B}_{|1|\oplus}P}\).\(\qed\) ◻
Theorem 11. \({\boldsymbol{c}oNP}\subseteq {\boldsymbol{B}_{|0|\oplus}P}\)
Proof. Let \(L\in{\boldsymbol{c}oNP}\). Then there is a polynomial-time predicate \(R\) and a polynomial \(p\) such that, for every input \(x\), \(x\in L \iff \nexists y \text{ such that } |y|=p(|x|) \text{ and } R(x,y)\). Define \(f(x)=||\{y\mid |y|=p(|x|)\wedge R(x,y)\}||\). Then \(f(x)\) is a \({\boldsymbol{\#}P}\) function and \(x\in L \iff f(x)=0\). We will use \(p=p(|x|)\) for readability. We define \(r=2p+1\) and \(\ell=4p+3\). Then both \(r\) and \(\ell\) are odd. We have \((2^r-1)f(x)<2^{r+p}<2^\ell\), since \(f(x)\le 2^p\). We next define \(H(x)=2^\ell+(2^r-1)f(x)\).
We first verify that \(H(x)\) is a valid \({\boldsymbol{\#}P}\) function. The term \(2^\ell\) is a \({\boldsymbol{\#}P}\) function, since a non-deterministic polynomial-time Turing machine can guess a string of length \(\ell\) and accept on every branch. The term \((2^r-1)f(x)\) is also a \({\boldsymbol{\#}P}\) function such that for each witness \(y\) counted by \(f(x)\), guess a string \(z\in\{0,1\}^r\) and accept if and only if \(z\neq 00\cdots 0\). This gives exactly \(2^r-1\) accepting paths for each such \(y\). Since \({\boldsymbol{\#}P}\) is closed under addition, \(H(x)\in{\boldsymbol{\#}P}\).
We next prove the main theorem with the following two lemmas.
Lemma 13. If \(x\in L\), then \(B_0(H(x))\not\equiv 0 \pmod 2\).
Proof. Suppose \(x\in L\). Then \(f(x)=0\) and \(H(x)=2^\ell\). The binary representation of \(2^\ell\) is a single \(1\) followed by \(\ell\) many \(0\)’s. Thus, \(B_0(H(x))=\ell\) which is odd, since \(\ell=4p+3\) is odd. Therefore, \(B_0(H(x))\not\equiv 0 \pmod 2\). ◻
Lemma 14. If \(x\notin L\), then \(B_0(H(x))\equiv 0 \pmod 2\).
Proof. Suppose \(x\notin L\). Then \(f(x)>0\), so \(1\le f(x)<2^r\). Let \(K=(2^r-1)f(x)\), so that \(H(x)=2^\ell+K\). We first show that \(K\) has exactly \(r\) many \(1\)’s in its binary representation. We can rewrite \(K\) as \(K=(2^r-1)f(x)=f(x)2^r-f(x)=(f(x)-1)2^r+(2^r-f(x))\). We can then write \(f(x)-1\) as an \(r\)-bit string \(a_{r-1}a_{r-2}\cdots a_0\), because \(0\le f(x)-1<2^r\). Also, \(2^r-f(x)=2^r-1-(f(x)-1)\), so the \(r\)-bit string for \(2^r-f(x)\) is the bitwise complement \(\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0\), where \(\overline{a}_i=1-a_i\). Therefore, \(K\) is represented by the two consecutive \(r\)-bit blocks \(\underbrace{a_{r-1}a_{r-2}\cdots a_0}_{f(x)-1}\underbrace{\overline{a}_{r-1}\overline{a}_{r-2}\cdots\overline{a}_0}_{2^r-f(x)}\).
Note that the term \((f(x)-1)2^r\) shifts the first block \(r\) positions to the left, and the term \(2^r-f(x)\) occupies the lower \(r\) positions. For each \(i\), exactly one of \(a_i\) and \(\overline{a}_i\) is equal to \(1\). So the two blocks contain exactly \(r\) many \(1\)’s altogether. Thus \(K\) has exactly \(r\) many \(1\)’s in its binary representation. Since \(K<2^\ell\), the binary representation of \(H(x)=2^\ell+K\) has one leading \(1\) in position \(\ell\), followed by the actual lower-order bit positions \(0,1,\dots,\ell-1\). These lower \(\ell\) positions contain exactly the bits of \(K\) in their corresponding positions. Since exactly \(r\) of these lower positions are \(1\)’s, the remaining \(\ell-r\) lower positions are \(0\)’s. Thus \(B_0(H(x))=\ell-r=(4p+3)-(2p+1)=2p+2\), which is even. Therefore, \(B_0(H(x))\equiv 0 \pmod 2\).\(\qed\) ◻
By the two lemmas, \(x\in L \iff B_0(H(x))\not\equiv 0 \pmod 2\). Therefore \(L\in{\boldsymbol{B}_{|0|\oplus}P}\). Since \(L\in{\boldsymbol{c}oNP}\) was any \(L\), then we can conclude that \({\boldsymbol{c}oNP}\subseteq {\boldsymbol{B}_{|0|\oplus}P}\).\(\qed\) ◻
Theorem 12. \({\boldsymbol{B}_{|0| \oplus}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. Let \(L\in{\boldsymbol{B}_{|0| \oplus}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))\not\equiv 0 \pmod 2\), where \(B_0(n)\) denotes the number of \(0\)’s bits in the standard binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
We claim that a \({\boldsymbol{P}}^{\boldsymbol{P}P}\) machine can recover the exact value of \(H(x)\). We can observe this by considering threshold questions of the form \(H(x)\ge z\), where \(1\le z\le 2^q\). Each such threshold question is in \({\boldsymbol{P}P}\). To see this, construct an auxiliary non-deterministic machine with exactly \(2^{q+1}\) computation paths as follows: One half of the paths simulate \(M(x)\) and contribute exactly \(H(x)\) accepting paths, while the other half accepts exactly \(2^q-z+1\) paths. Therefore, the auxiliary machine has exactly \(H(x)+(2^q-z+1)\) accepting paths. Its majority threshold is \(2^q\), and \(H(x)+(2^q-z+1)>2^q\) if and only if \(H(x)\ge z\). Thus, the threshold language \(\{(x,z):H(x)\ge z\}\) is in \({\boldsymbol{P}P}\).
Using this \({\boldsymbol{P}P}\) oracle, a deterministic polynomial-time machine can recover \(H(x)\) by binary search over the interval \(0\le H(x)\le 2^q\). Once it has recovered \(H(x)\), it can write down the standard binary representation of \(H(x)\), compute \(B_0(H(x))\), and accept exactly when \(B_0(H(x))\not\equiv 0 \pmod 2\). Therefore, \(L\in{\boldsymbol{P}}^{\boldsymbol{P}P}\). Since \(L\in{\boldsymbol{B}_{|0| \oplus}P}\) was any \(L\), then we can conclude that \({\boldsymbol{B}_{|0| \oplus}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\).\(\qed\) ◻
Theorem 13. \({\boldsymbol{B}_{|1| \oplus}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. Let \(L\in{\boldsymbol{B}_{|1| \oplus}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_1(H(x))\not\equiv 0 \pmod 2\), where \(B_1(n)\) denotes the number of \(1\)’s bits in the standard binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
As shown in the previous theorem, threshold questions of the form \(H(x)\ge z\), where \(1\le z\le 2^q\), are in \({\boldsymbol{P}P}\). Therefore, using a \({\boldsymbol{P}P}\) oracle, a deterministic polynomial-time machine can recover the exact value of \(H(x)\) by binary search over the interval \(0\le H(x)\le 2^q\). Once it has recovered \(H(x)\), the machine can write down the standard binary representation of \(H(x)\), compute \(B_1(H(x))\), and accept exactly when \(B_1(H(x))\not\equiv 0 \pmod 2\). Therefore, \(L\in{\boldsymbol{P}}^{\boldsymbol{P}P}\). Since \(L\in{\boldsymbol{B}_{|1| \oplus}P}\) was any \(L\), then we can conclude that \({\boldsymbol{B}_{|1| \oplus}P}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\).\(\qed\) ◻
Theorem 14. \({\boldsymbol{B}_{|1| \oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|0| \oplus}P}}\).
Proof. Let \(L\in{\boldsymbol{B}_{|1| \oplus}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_1(H(x))\not\equiv 0 \pmod 2\), where \(B_1(n)\) denotes the number of \(1\)’s bits in the binary representation of \(n\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomially bounded function \(q(n)\) such that, on every input \(x\) of length \(n\), the machine \(M\) uses exactly \(q(n)\) non-deterministic bits and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
We now define a new \({\boldsymbol{\#}P}\) function \(G(x)=2^{q+1}+H(x)\). The function \(G(x)\) is in \({\boldsymbol{\#}P}\), because \(H(x)\) is in \({\boldsymbol{\#}P}\) and the length-dependent term \(2^{q+1}\) is in \({\boldsymbol{\#}P}\). Indeed, a non-deterministic polynomial-time Turing machine can guess a string of length \(q+1\) and accept on every branch, giving exactly \(2^{q+1}\) accepting paths. Since \({\boldsymbol{\#}P}\) is closed under addition, \(G(x)\in{\boldsymbol{\#}P}\).
We now consider the following language \(O=\{x:B_0(G(x))\not\equiv 0 \pmod 2\}\). By definition, \(O\in{\boldsymbol{B}_{|0| \oplus}P}\). We will show that \(L\) can be decided in polynomial time with oracle access to \(O\). Since \(0\le H(x)\le 2^q\), the value \(H(x)\) only affects the lower-order bit positions \(0,1,\dots,q\) of \(G(x)\). Therefore, the standard binary representation of \(G(x)=2^{q+1}+H(x)\) has a leading \(1\) in position \(q+1\), followed by exactly \(q+1\) lower-order bit positions encoding \(H(x)\). Among these \(q+1\) lower-order positions, exactly \(B_1(H(x))\) positions contain \(1\)’s. Therefore, \(B_0(G(x))=(q+1)-B_1(H(x))\). Taking this equation modulo \(2\), we get \(B_0(G(x))\equiv q+1-B_1(H(x)) \pmod 2\). Since subtraction is the same as addition modulo \(2\), this is equivalent to \(B_0(G(x))\equiv q+1+B_1(H(x)) \pmod 2\). Therefore, \(B_1(H(x))\equiv B_0(G(x))+(q+1) \pmod 2\).
A deterministic polynomial-time oracle machine can decide \(L\) as follows. On input x, it computes \(q = q(|x|)\) and queries the oracle \(O\) on input \(x\). If \(q+1\) is even, then \(B_1(H(x))\) and \(B_0(G(x))\) have the same parity, so then the machine accepts exactly when the oracle says yes. If \(q+1\) is odd, then \(B_1(H(x))\) and \(B_0(G(x))\) have opposite parity, so then the machine accepts exactly when the oracle says no.
We next prove the main theorem with the following two lemmas
Lemma 15. If \(x\in L\), then the oracle machine accepts \(x\).
Proof. Assume \(x\in L\). Since \(L\in{\boldsymbol{B}_{|1| \oplus}P}\) via \(H(x)\), we have \(B_1(H(x))\not\equiv 0 \pmod 2\). Thus, \(B_1(H(x))\) is odd. If \(q+1\) is even, then \(B_1(H(x))\) and \(B_0(G(x))\) have the same parity. Thus, \(B_0(G(x))\) is odd, so the oracle says yes, and the machine accepts. If \(q+1\) is odd, then \(B_1(H(x))\) and \(B_0(G(x))\) have opposite parity. Thus, \(B_0(G(x))\) is even, so the oracle says no, and the machine accepts by construction. Therefore, in both cases, the oracle machine accepts \(x\).\(\qed\) ◻
Lemma 16. If \(x\notin L\), then the oracle machine rejects \(x\).
Proof. Assume \(x\notin L\). Since \(L\in{\boldsymbol{B}_{|1| \oplus}P}\) via \(H(x)\), we have \(B_1(H(x))\equiv 0 \pmod 2\). Thus \(B_1(H(x))\) is even. If \(q+1\) is even, then \(B_1(H(x))\) and \(B_0(G(x))\) have the same parity. Thus, \(B_0(G(x))\) is even, so the oracle says no, and the machine rejects. If \(q+1\) is odd, then \(B_1(H(x))\) and \(B_0(G(x))\) have opposite parity. Thus, \(B_0(G(x))\) is odd, so the oracle says yes, and the machine rejects by construction. Therefore, in both cases, the oracle machine rejects \(x\).\(\qed\) ◻
The two lemmas show that the deterministic polynomial-time oracle machine accepts exactly the strings in \(L\). Therefore, \(L\in{\boldsymbol{P}}^{{\boldsymbol{B}_{|0| \oplus}P}}\). Since \(L\in{\boldsymbol{B}_{|1| \oplus}P}\) was for any \(L\), then we can conclude that \({\boldsymbol{B}_{|1| \oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|0| \oplus}P}}\).\(\qed\) ◻
Theorem 15. \({\boldsymbol{B}_{|0|\oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).
Proof. Let \(L\in{\boldsymbol{B}_{|0|\oplus}P}\). Then there exists a \({\boldsymbol{\#}P}\) function \(H(x)\) such that \(x\in L \iff B_0(H(x))\not\equiv 0 \pmod 2\). Since \(H(x)\) is a \({\boldsymbol{\#}P}\) function, there is a non-deterministic polynomial-time Turing machine \(M\) and a polynomial \(q\) such that, without loss of generality, on every input \(x\) of length \(n\), the machine \(M\) has exactly \(2^{q(n)}\) computation paths and \(H(x)=\#\operatorname{acc}_{M}(x)\). Thus, \(0\le H(x)\le 2^{q(|x|)}\). We will use \(q=q(|x|)\) for readability.
Let \(\ell(n)\) denote the number of bits in the standard binary representation of \(n\), with the convention that the standard binary representation of \(0\) is \(0\), so \(\ell(0)=1\). Since \(B_0(n)+B_1(n)=\ell(n)\), we have \(B_0(n)\equiv \ell(n)+B_1(n)\pmod 2\). Therefore, to decide whether \(B_0(H(x))\) is odd, it is enough to determine the parity of \(B_1(H(x))\) and the parity of \(\ell(H(x))\).
Define \(r=2q+1\) and \(G(x)=(2^r-1)H(x)\). Also, for each \(i\in\{0,1,\dots,q\}\), define \(H_i(x)=H(x)+2^i\). The functions \(G(x)\), \(H(x)\), and \(H_i(x)\) are all \({\boldsymbol{\#}P}\) functions. The function \(G(x)\) is obtained by multiplying each accepting path counted by \(H(x)\) by \(2^r-1\) accepting choices, and each \(H_i(x)\) is the sum of \(H(x)\) and the length-dependent constant \(2^i\). By tagging the query as one of these three types, all queries can be combined into a single oracle language \(O\in{\boldsymbol{B}_{|1|\oplus}P}\). The oracle says yes exactly when the tagged \({\boldsymbol{\#}P}\) value has an odd number of \(1\)’s in its binary representation.
The deterministic polynomial-time oracle machine works as follows. On input \(x\), it first queries the oracle for \(G(x)\). If \(H(x)=0\), then \(G(x)=0\), so \(B_1(G(x))=0\), and the oracle returns no. If \(H(x)>0\), then \(1\le H(x)<2^r\), and by the complementary-block argument, \((2^r-1)H(x)\) has exactly \(r\) many \(1\)’s in its binary representation. Since \(r=2q+1\) is odd, the oracle returns yes. Thus, the first query returns no exactly when \(H(x)=0\), and returns yes exactly when \(H(x)>0\). If the first query returns no, the machine accepts immediately, because then \(H(x)=0\) and \(B_0(0)=1\) is odd.
If the first query returns yes, then \(H(x)>0\). The machine queries the oracle for \(H(x)\) itself, obtaining the parity of \(B_1(H(x))\). It remains to determine the parity of \(\ell(H(x))\). Let \(h\) be the index of the most significant \(1\)-bit of \(H(x)\), so \(\ell(H(x))=h+1\). Since \(H(x)\le 2^q\), we have \(h\le q\).
To find \(h\), the machine uses the queries for \(H_i(x)=H(x)+2^i\). Let \(c_i\) be the number of consecutive \(1\)’s in the binary representation of \(H(x)\) starting at position \(i\) and moving upward; if the bit in position \(i\) is \(0\), then \(c_i=0\). Adding \(2^i\) changes those \(c_i\) consecutive \(1\)’s to \(0\)’s and changes the next \(0\) to a \(1\), so \(B_1(H_i(x))\equiv B_1(H(x))+1+c_i\pmod 2\). Thus the oracle queries for \(H_i(x)\) allow the machine to compute \(c_i\pmod 2\) for every \(i\).
The machine checks the indices in decreasing order, \(i=q,q-1,\dots,0\), and stops at the first index for which \(c_i\) is odd. This index is exactly \(h\), the position of the most significant \(1\)-bit of \(H(x)\), because for every \(i>h\) the bit in position \(i\) is \(0\), so \(c_i=0\), while at \(i=h\) the bit is \(1\) and the next higher bit is \(0\), so \(c_h=1\). Thus the machine correctly finds \(h\) and computes \(\ell(H(x))=h+1\). It already knows \(B_1(H(x))\pmod 2\), so using \(B_0(H(x))\equiv \ell(H(x))+B_1(H(x))\pmod 2\), it computes \(B_0(H(x))\pmod 2\) and accepts exactly when this parity is \(1\).
We next prove the main theorem with the following two lemmas.
Lemma 17. If \(x\in L\), then the oracle machine accepts \(x\).
Proof. Assume \(x\in L\). Since \(L\in{\boldsymbol{B}_{|0|\oplus}P}\) via \(H(x)\), we have \(B_0(H(x))\not\equiv 0\pmod 2\). Thus \(B_0(H(x))\) is odd.
Suppose \(H(x)=0\). The first oracle query is the query for \(G(x)=(2^r-1)H(x)\). Since \(H(x)=0\), we have \(G(x)=0\). Hence \(B_1(G(x))=B_1(0)=0\), which is even, so the \({\boldsymbol{B}_{|1|\oplus}P}\) oracle returns no on this first query. By construction, when the first query for \(G(x)\) returns no, the oracle machine concludes that \(H(x)=0\) and accepts immediately.
Suppose \(H(x)>0\). Then the first oracle query for \(G(x)\) returns yes, because \(G(x)=(2^r-1)H(x)\) has exactly \(r\) many \(1\)’s in its binary representation and \(r=2q+1\) is odd. Therefore, the oracle machine continues. It then queries the oracle for \(H(x)\) itself to obtain the parity of \(B_1(H(x))\), and it uses the queries for \(H_i(x)=H(x)+2^i\) to compute the true binary length \(\ell(H(x))\). The machine then computes the parity of \(B_0(H(x))\) by using the identity \(B_0(H(x))\equiv \ell(H(x))+B_1(H(x))\pmod 2\). Since \(x\in L\) and \(L\) is recognized by the condition \(B_0(H(x))\not\equiv 0\pmod 2\), the number \(B_0(H(x))\) is odd. Therefore, the computed parity is \(1\), and by construction the oracle machine accepts.\(\qed\) ◻
Lemma 18. If \(x\notin L\), then the oracle machine rejects \(x\).
Proof. Assume \(x\notin L\). Since \(L\in{\boldsymbol{B}_{|0|\oplus}P}\) via \(H(x)\), we have \(B_0(H(x))\equiv 0\pmod 2\). Thus \(B_0(H(x))\) is even.
Suppose \(H(x)>0\). Then the first oracle query is the query for \(G(x)=(2^r-1)H(x)\). Since \(H(x)>0\), the number \(G(x)=(2^r-1)H(x)\) has exactly \(r\) many \(1\)’s in its binary representation. Since \(r=2q+1\) is odd, the oracle returns yes on this first query. By construction, when the first query for \(G(x)\) returns yes, the oracle machine concludes that \(H(x)>0\) and continues. It then queries the oracle for \(H(x)\) itself to obtain the parity of \(B_1(H(x))\), and it uses the queries for \(H_i(x)=H(x)+2^i\) to compute the true binary length \(\ell(H(x))\). The machine then computes the parity of \(B_0(H(x))\) by using the identity \(B_0(H(x))\equiv \ell(H(x))+B_1(H(x))\pmod 2\). Since \(x\notin L\) and \(L\) is recognized by the condition \(B_0(H(x))\not\equiv 0\pmod 2\), the number \(B_0(H(x))\) is even. Therefore, the computed parity is \(0\), and by construction the oracle machine rejects. \(\qed\) ◻
The two lemmas show that the oracle machine decides \(L\) using an oracle in \({\boldsymbol{B}_{|1|\oplus}P}\). Therefore, \(L\in{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\). Since \(L\in{\boldsymbol{B}_{|0|\oplus}P}\) was for any \(L\), then we can conclude that \({\boldsymbol{B}_{|0|\oplus}P}\subseteq{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).\(\qed\) ◻
Theorem 16. \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).
Proof. By the previous result, we have \({\boldsymbol{B}_{|1|\oplus}P}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\). Therefore, every oracle query to a language in \({\boldsymbol{B}_{|1|\oplus}P}\) can be simulated by a deterministic polynomial-time computation with access to a \({\boldsymbol{B}_{|0|\oplus}P}\) oracle. Thus, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\subseteq {\boldsymbol{P}}^{{\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}}\). Since nested deterministic polynomial-time oracle computations collapse, we have \({\boldsymbol{P}}^{{\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\). Therefore, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\subseteq {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\).
Similarly, by the previous result, we have \({\boldsymbol{B}_{|0|\oplus}P}\subseteq{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\). Therefore, every oracle query to a language in \({\boldsymbol{B}_{|0|\oplus}P}\) can be simulated by a deterministic polynomial-time computation with access to a \({\boldsymbol{B}_{|1|\oplus}P}\) oracle. Thus, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\subseteq {\boldsymbol{P}}^{{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}}\). Again, nested deterministic polynomial-time oracle computations collapse, so \({\boldsymbol{P}}^{{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\). Therefore, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\subseteq{\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).
Combining the two containments, we get \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\). ◻
Theorem 17. \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\)
Proof. By the previous theorem, we have \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\). It remains to show that this is contained in \({\boldsymbol{P}}^{\boldsymbol{P}P}\). By the previous containment theorem, we have \({\boldsymbol{B}_{|0|\oplus}P}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). Therefore, any oracle query to a language in \({\boldsymbol{B}_{|0|\oplus}P}\) can be simulated by a deterministic polynomial-time computation with access to a \({\boldsymbol{P}P}\) oracle. Thus, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\subseteq {\boldsymbol{P}}^{{\boldsymbol{P}}^{\boldsymbol{P}P}}\). Since nested deterministic polynomial-time oracle computations collapse, we have \({\boldsymbol{P}}^{{\boldsymbol{P}}^{\boldsymbol{P}P}}={\boldsymbol{P}}^{\boldsymbol{P}P}\).
Therefore, \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}\subseteq{\boldsymbol{P}}^{\boldsymbol{P}P}\). Using \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\), then we can conclude that \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\subseteq {\boldsymbol{P}}^{\boldsymbol{P}P}\). ◻
Location of our bit-counting complexity classes in the complexity hierarchy.
We introduced and studied a family of complexity classes defined by applying bit-counting predicates to the binary representation of \({\boldsymbol{\#}P}\) functions. Our first observation was that applying simple bit-counting predicates to the binary expansion of the number of accepting path count can define some well known complexity classes, such as \({\boldsymbol{N}P}\), \({\boldsymbol{C}oNP}\) and \({\boldsymbol{C}_=P}={\boldsymbol{M}NS}\). Most interestingly, we also obtained some nontrivial complexity classes and divided them into two subcategories as comparison and parity based bit-counting complexity classes.
The comparison based bit-counting complexity classes \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|>|1|}P}\) and \({\boldsymbol{B}_{|0|<|1|}P}\) capture whether the number of 0’s bits and 1’s bits in a \({\boldsymbol{\#}P}\) value are equal, zero, or one dominant. We proved that each one of these complexity classes is strong enough to contain \({\boldsymbol{P}P}\). We also established an upper bounds for these complexity classes. Since a \({\boldsymbol{P}}^{\boldsymbol{P}P}\) machine can recover the exact value of a \({\boldsymbol{\#}P}\) function using threshold queries and then inspect its binary representation directly, each one of the comparison based bit-counting complexity classes is contained in \({\boldsymbol{P}}^{\boldsymbol{P}P}\). By combining these two results, we obtained the equivalence at the Turing level \({\boldsymbol{P}}^{\boldsymbol{P}P} = {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|=|1|}P}} = {\boldsymbol{P}}^{{\boldsymbol{B}_{|0|>|1|}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|0|<|1|}P}}\).
For the parity based bit-counting complexity classes, \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\), we proved that both contain \({\boldsymbol{N}P}\) and \({\boldsymbol{c}oNP}\). These containments show that the parity predicates applied to the number of 0’s bits or 1’s bits of a \({\boldsymbol{\#}P}\) count are already powerful enough to encode existential and universal non-deterministic behavior. At the same time, both classes are contained in \({\boldsymbol{P}}^{\boldsymbol{P}P}\), again because \({\boldsymbol{P}}^{\boldsymbol{P}P}\) can reconstruct the relevant \({\boldsymbol{\#}P}\) count and compute the desired bit parity in polynomial time. We further showed that the two parity based bit-counting complexity classes are equivalent at the Turing level \({\boldsymbol{P}}^{{\boldsymbol{B}_{|0|\oplus}P}}={\boldsymbol{P}}^{{\boldsymbol{B}_{|1|\oplus}P}}\).
Our results demonstrated that bit-counting complexity classes form a useful intermediate framework for studying the relationship between non-deterministic and probabilistic counting complexity. However, there are still more avenues to explore. For instance, we were not able to prove much with regards to \({\boldsymbol{B}_{|0|=0}P}\) and \({\boldsymbol{B}_{|0|>0}P}\), other than to show that by definition they are equal to \({\boldsymbol{C}_{=}P}={\boldsymbol{M}NS}\) and \({\boldsymbol{C}oC_{=}P}={\boldsymbol{C}oMNS}\), respectively. Furthermore, we were also not able to show how the classical complexity classes \({\boldsymbol{\oplus} P}\) or \({\boldsymbol{U}S}\) relate to any one of our bit-counting complexity classes.
In addition, what is the upper bound for the parity based bit-counting complexity classes? Are complexity classes \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\) contained in some level of the polynomial-hierarchy, \({\boldsymbol{P}H}\) [8]? Or do complexity classes \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\) contain some level of PH other than NP and CoNP? It would also be of interest to see if \({\boldsymbol{B}_{|0|\oplus}P} ^ {\boldsymbol{B}_{|0|\oplus}P}\) collapses to \({\boldsymbol{B}_{|0|\oplus}P}\) or if it gets more powerful as more \({\boldsymbol{B}_{|0|\oplus}P}\) oracles are added. Clearly, the same question could be asked about the complexity class \({\boldsymbol{B}_{|1|\oplus}P}\). Furthermore, can we show whether \({\boldsymbol{B}_{|1|\oplus}P}^{{\boldsymbol{B}_{|0|\oplus}P}} \subseteq {\boldsymbol{B}_{|0|\oplus}P}^{{\boldsymbol{B}_{|1|\oplus}P}}\) or \({\boldsymbol{B}_{|0|\oplus}P}^{{\boldsymbol{B}_{|1|\oplus}P}} \subseteq {\boldsymbol{B}_{|1|\oplus}P}^{{\boldsymbol{B}_{|0|\oplus}P}}\) hold? We can also create four different parity based bit-counting hierarchies as follows:
-\({\boldsymbol{B}_{|1|\oplus}H}\), like in \({\boldsymbol{P}H}\), we use \({\boldsymbol{B}_{|1|\oplus}P}\) and it’s complement at each level.
-\({\boldsymbol{B}_{|0|\oplus}H}\), like in \({\boldsymbol{P}H}\), we use \({\boldsymbol{B}_{|0|\oplus}P}\) and it’s complement at each level.
-\({\boldsymbol{B}_{|1|\oplus}AH}\), we start with \({\boldsymbol{B}_{|1|\oplus}P}\) and then alternate between \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\) at each level.
-\({\boldsymbol{B}_{|0|\oplus}AH}\), we start with \({\boldsymbol{B}_{|0|\oplus}P}\) and then alternate between \({\boldsymbol{B}_{|1|\oplus}P}\) and \({\boldsymbol{B}_{|0|\oplus}P}\) at each level.
Do hierarchies \({\boldsymbol{B}_{|1|\oplus}H}\), \({\boldsymbol{B}_{|0|\oplus}H}\), \({\boldsymbol{B}_{|1|\oplus}AH}\) and \({\boldsymbol{B}_{|0|\oplus}AH}\) contain \({\boldsymbol{P}H}\), contain each other or equal to each other?
There is also the case of semantic [9] [5] variants of our comparison and parity based bit-counting complexity classes. So instead of using \(\Leftrightarrow\) in the definition of our complexity classes \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|>|1|}P}\), \({\boldsymbol{B}_{|0|<|1|}P}\), \({\boldsymbol{B}_{|0|\oplus}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\), we can change it to \(\Rightarrow\) and make that the acceptance criterion. Then for \({\boldsymbol{B}_{|0|=|1|}P}\), \({\boldsymbol{B}_{|0|<|1|}P}\) and \({\boldsymbol{B}_{|1|\oplus}P}\), we can make the rejection criterion zero accepting paths and for \({\boldsymbol{B}_{|0|>|1|}P}\) and \({\boldsymbol{B}_{|0|\oplus}P}\) we can make the rejection criterion one accepting path. This would yield natural semantic variants of our comparison and parity based bit-counting complexity classes and would result in the following five containments:
-\({\boldsymbol{B}_{|0|=|1|}SP} \subseteq {\boldsymbol{B}_{|0|=|1|}P}\)
-\({\boldsymbol{B}_{|0|<|1|}SP} \subseteq {\boldsymbol{B}_{|0|<|1|}P}\)
-\({\boldsymbol{B}_{|0|>|1|}SP} \subseteq {\boldsymbol{B}_{|0|>|1|}P}\)
-\({\boldsymbol{B}_{|0|\oplus}SP} \subseteq {\boldsymbol{B}_{|0|\oplus}P}\)
-\({\boldsymbol{B}_{|1|\oplus}SP} \subseteq {\boldsymbol{B}_{|1|\oplus}P}\)
The important question we now have is whether any of the theorems we proved in this paper with regards to our bit-counting complexity classes also hold for their semantic variants. Can we also prove any containment amongst our semantic bit-counting complexity classes or any classical complexity class?
One last point is that all of the recently discovered Mersenne primes have an odd number of 1’s bits, so \({\boldsymbol{B}_{|1|\oplus}P} \cap {\boldsymbol{B}_{|0|=0}P}\) might be of an interest for exploration.