From the 1 of 4 linked papers with an AI index.
4 papers
Even more properties of parity based bit-counting complexity classes
Tayfun Pay
We study several additional properties of parity based bit-counting complexity classes and . We first prove that ${\bf MNS}\subseteq{…
Additional properties of parity based bit-counting complexity classes and hierarchies
Tayfun Pay
The paper studies parity‑based bit‑counting complexity classes B_{|0|⊕}P and B_{|1|⊕}P, establishing closure properties, relationships to US and ⊕P, and using them to define hierar…
Bit-counting complexity classes
Tayfun Pay
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.…
A Note On The Natural Range Of Unambiguous-SAT
Tayfun Pay
We discuss the natural range of the Unambiguous-SAT problem with respect to the number of clauses. We prove that for a given Boolean formula in precise conjunctive normal form with…