The class on published oracle machines
DefinitionCoverTime537_SpecifiedStart_Supplement_OracleClassescomputational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
On the published finite multitape oracle machines (with charged query writing), a language is in when one machine, with time bound and certificate length fixed polynomials, halts within steps on every input and every certificate of length , and
A language is in when there are languages (no oracle) and such that . Here (strict majority) and are the published definitions, and the counting hierarchy is the published one: , , .
These classes state Theorem 3 of the paper.
Formalization Note Only the relativized NP predicate is new; it uses the same machines, configurations and polynomial bounds as the published PP and P predicates.
Definition code
import Mathlib
import Definitions.Def_APSCounting893_Main_CountingHierarchy
namespace CoverTime537.SpecifiedStart.Supplement
open APSCounting893.Main
/-- NP relative to an oracle `A`, on the published finite oracle machines:
a uniform polynomial-time verifier with certificates of one exact polynomial
length (written on the random tape); `x ∈ L` iff some certificate is accepted. -/
def InOracleNP (A L : Language) : Prop :=
∃ (M : APSCounting893.Main.OracleMachine) (c d a b : ℕ), RunsInTime M A c d a b ∧
∀ x : Word, L x ↔ ∃ w : Word, w.length = polyBound a b x.length ∧
(machineRun M A x w (polyBound c d x.length)).answer = some true
/-- `L ∈ P^{NP^{PP}}`: a deterministic polynomial-time decider with oracle `B`,
where `B ∈ NP^A` and `A ∈ PP` (unrelativized: the empty oracle). -/
def InPNPPP (L : Language) : Prop :=
∃ A B : Language, InOraclePP (fun _ => False) A ∧ InOracleNP A B ∧ InOracleP B L
end CoverTime537.SpecifiedStart.Supplement
Source
Ryan Aghazadeh, How Hard Is It to Compute Cover Time?, STOC 2027 submission #537 (October 2026), papers/stoc2027-537/source.pdf, SHA-256 4487efe2e616b5ed1b0e9a8a4172a4b53fd492c5d9ad4717ed4921b088564fd8, p.3 (Theorem 3 and 'Here P^{NP^{PP}} denotes deterministic polynomial time with an NP^{PP} oracle'), Appendix C p.23 (definition of CH)