Bounded strict-majority oracle queries lie in PP
ProvedAPSCounting893.Main.bounded_majority_oracle_ppapscounting-hierarchymajorityoracle-machines
Let be any language of finite binary words and let , where are fixed natural numbers. The language
belongs to . The majority is strict, and the case of a zero-length random seed is included. The pairing is the fixed prefix-free word encoding used throughout this development.
The conclusion uses an actual finite oracle machine with one uniform polynomial time bound for every input and every seed. It provides the majority layer in uniform threshold-gate evaluation.
Preamble
import Definitions.Def_APSCounting893_Main_OracleProofPrimitives set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.bounded_majority_oracle_pp (A : Language) (a b : ℕ) :
InOraclePP A (fun x =>
2^polyBound a b x.length < 2*Set.ncard
{w : Word | w.length=polyBound a b x.length ∧ A (pairWord x w)}) := by sorrySource
Andrews, Garg and Schost, Hilbert’s Nullstellensatz is in the Counting Hierarchy, https://arxiv.org/abs/2602.17904, Lemma 6.3, pp.45–46 (one strict-majority oracle layer). Used in Agarwal, Hari, Pandey and Shukla, STOC 2027 submission #893, Theorem 6.4, pp.25–26, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf.