Additional properties of parity based bit-counting complexity classes and hierarchies

Jul 16, 2026

Upload by Noah

Studies parity based bit-counting complexity classes B|0|⊕P and B|1|⊕P, establishing closure under complement and strengthening known containments by proving B|1|⊕P ⊆ B|0|⊕P. Shows relationships with US via US ⊆ PB|1|⊕P and US ⊆ PB|0|⊕P, and analyzes characteristic functions whose B|1|⊕P output is the Prouhet–Thue–Morse sequence. Uses finite contiguous blocks to determine parity, derives ⊕P ⊆ PB|0|⊕P and ⊕P ⊆ PB|1|⊕P, then builds parity based hierarchies between PH and CH.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages20

Reading Time50 min

AccessFree to download

Introduction

Definitions and containments

Some classical complexity classes and hierarchies

Parity based bit-counting complexity classes and hierarchies

arXiv :2607 .04048v 1 [ cs .CC] 4 Jul 2026 Additional properties of parity based bit-counting complexity classes and hierarchies Tayfun Pay [tpay@gradcenter.cuny.edu](tpay@gradcenter.cuny.edu) Abstract. We study some properties of the parity based bit-counting complexity classes B|0|⊕P and B|1|⊕P. We first show that both of these complexity classes are closed under complement and prove that B|1|⊕P ⊆ B |0|⊕P. We then prove that US ⊆ PB |1| ⊕ P and US ⊆ PB |0| ⊕ P . We then study the characteristic functions of the parity based bit-counting complexity classes, where the characteristic function of B |1|⊕P outputs the Prouhet–Thue–Morse sequence. We then prove that a finite contiguous block of these sequences yield the parity of the starting number and then prove that ⊕P ⊆ PB |0| ⊕ P and ⊕P ⊆ PB |1| ⊕ P . We then use the parity based bit-counting complexity classes to define various hierarchies and show that they all contain PH and are contained in CH. 1 Introduction We study some properties of parity based bit-counting complexity classes B|0|⊕P and B |1|⊕P that were defined in [P26] . We first show that the parity based bit-counting complexity classes B |0|⊕P and B |1|⊕P are closed under complement. We also improve upon the containment proven in [P26], namely B|1|⊕P ⊆ PB |0|⊕P , and prove that B |1|⊕P ⊆ B |0|⊕P. We then show the relationship between the parity based bit-counting complexity classes and the complexity class US by proving that US ⊆ PB|1|⊕P and US ⊆ PB|0|⊕P . We then explore the relationship between the parity based bit-counting complexity classes B |0|⊕P and B |1|⊕P and the classical parity based complexity class ⊕P. We first define the infinite sequences that correspond to the output of the characteristic functions of B |0|⊕P and B |1|⊕P, where the one produced by the characteristic function of B|1|⊕P is the Prouhet–Thue–Morse sequence. We then prove that for both of these sequences, a finite contiguous block of size four is enough to determine the parity of the first value in that contiguous block of size four. We then use this information to prove that ⊕P ⊆ PB |0| ⊕ P and ⊕P ⊆ PB |1| ⊕ P . We then introduce four parity based bit-counting hierarchies inspired by the polynomial hierarchy, PH. The ΣB|0|⊕H and ΣB|1|⊕H hierarchies use the parity based bit-counting complexity classes B |0|⊕P and B |1|⊕P respectively, and mirror the Σ side of the PH. Whereas the ∆B |0|⊕H and ∆B |1|⊕H hierarchies once again use the parity based bit-counting complexity classes B |0|⊕P and B|1|⊕P respectively, and mirror the ∆ part of the PH. We then show that 2 Tayfun Pay ΣB |0|⊕H equals ΣB|1|⊕H and ∆B|0|⊕H equals ∆B|1|⊕H, when you take their unions over all levels. After that, we prove that they all contain PH. We then define the alternating versions of these hierarchies as AltΣB |0|⊕H, AltΣB |1|⊕H, Alt∆B |0|⊕H and Alt∆B |1|⊕H. These hierarchies have the opposite parity based bit-counting complexity class at their even valued levels. We show that AltΣB |0|⊕H equals AltΣB |1|⊕H and that Alt∆B |0|⊕H equals Alt∆B |1|⊕H, when you take their unions over all levels. We then show that they also equal their non-alternating counterparts. Finally, we show that the counting hierarchy, CH, contains the parity based bit-counting hierarchies. These results illustrate the importance of the parity based bit-counting complexity classes. As far as we know, B |0|⊕P and B |1|⊕P are the first complexity classes that contain the complexity classes NP, US and ⊕P at the same time, of course other than PPP . Furthermore, we establish the existence of well defined hierarchies between PH and CH. 2 Definitions and containments 2.1 Some classical complexity classes and hierarchies 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 ∈ L ⇔ ||{y| |y| = p (|x|) ∧ R(x, y)}|| > 0 Definition 2 . A language L is in complexity class CoNP, if there ex

FAQs

What key closure and containment properties are proved for B|0|⊕P and B|1|⊕P?

Both B|0|⊕P and B|1|⊕P are shown to be closed under complement. The work proves the stronger containment B|1|⊕P ⊆ B|0|⊕P (improving earlier results).

How are the classes B|0|⊕P and B|1|⊕P related to US?

The document establishes US ⊆ PB|1|⊕P and US ⊆ PB|0|⊕P, connecting the parity based bit-counting framework to the unique-solution class US.

What role does the Prouhet–Thue–Morse sequence play?

The characteristic function of B|1|⊕P outputs the Prouhet–Thue–Morse sequence. The paper then shows that finite contiguous blocks of these sequences determine the parity of the starting index, enabling containments involving ⊕P.

Jul 16, 2026

Upload by Noah