← 研踪 PaperTrailarXiv:2608.04484 · v2
Even more properties of parity based bit-counting complexity classes
首次提交 2026-08-05 14:17
版本更新 2026-10-27 13:15
雷达观测 2026-10-29 00:35
摘要
We investigate several additional properties of parity based bit-counting complexity classes ${\bf B_{|0|\oplus}P}$ and ${\bf B_{|1|\oplus}P}$. We first prove that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then build upon the four consecutive value theorem from \cite{P26b} and develop a bit recovery procedure that reconstructs the binary representation of a ${\bf \#P}$ value one bit at a time by querying appropriately padded and shifted versions of that value. Using this procedure, we prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. Furthermore, since this procedure recovers the complete numerical output of a ${\bf \#P}$ function, it also establishes the functional containments of ${\bf \#P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \#P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We additionally demonstrate that caching repeated oracle queries reduces the number of distinct queries required for the bit recovery procedure from $4n$ to $2n+2$. Finally, we prove that parity based bit-counting hierarchies ${\bf ΣB_{|0|\oplus}H}$, ${\bf ΣB_{|1|\oplus}H}$, ${\bf ΔB_{|0|\oplus}H}$ and ${\bf ΔB_{|1|\oplus}H}$ contain ${\bf CH}$. As a result, these hierarchies coincide with ${\bf CH}$ since the reverse containments were already established in \cite{P26b}.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-27 13:15 · 最新观测版本
Even more properties of parity based bit-counting complexity classes
We investigate several additional properties of parity based bit-counting complexity classes ${\bf B_{|0|\oplus}P}$ and ${\bf B_{|1|\oplus}P}$. We first prove that ${\bf C_=P}={\bf ES}={\bf MNS}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}={\bf P}^{{\bf B_{|0|\oplus}P}}$. We then build upon the four consecutive value theorem from \cite{P26b} and develop a bit recovery procedure that reconstructs the binary representation of a ${\bf \#P}$ value one bit at a time by querying appropriately padded and shifted versions of that value. Using this procedure, we prove that ${\bf PP}\subseteq{\bf P}^{{\bf B_{|1|\oplus}P}}$ and ${\bf PP}\subseteq{\bf P}^{{\bf B_{|0|\oplus}P}}$, which consequently yields ${\bf P}^{\bf PP}={\bf P}^{\bf B_{|0|\oplus}P}={\bf P}^{\bf B_{|1|\oplus}P}$. Furthermore, since this procedure recovers the complete numerical output of a ${\bf \#P}$ function, it also establishes the functional containments of ${\bf \#P}\subseteq{\bf FP}^{{\bf B_{|1|\oplus}P}}$ and ${\bf \#P}\subseteq{\bf FP}^{{\bf B_{|0|\oplus}P}}$. We additionally demonstrate that caching repeated oracle queries reduces the number of distinct queries required for the bit recovery procedure from $4n$ to $2n+2$. Finally, we prove that parity based bit-counting hierarchies ${\bf ΣB_{|0|\oplus}H}$, ${\bf ΣB_{|1|\oplus}H}$, ${\bf ΔB_{|0|\oplus}H}$ and ${\bf ΔB_{|1|\oplus}H}$ contain ${\bf CH}$. As a result, these hierarchies coincide with ${\bf CH}$ since the reverse containments were already established in \cite{P26b}.
查看此版本解读 →查看此版本原文 ↗