Theorem 3 — Cover-Time and Max-Cover-Time in and CH
OpenCoverTime537.SpecifiedStart.Supplement.theorem_3computational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Both exact comparison languages
belong to , and both belong to the counting hierarchy .
The languages are over all valid encodings of connected simple undirected unweighted graphs given by neighbor lists, with arbitrary signed binary rational thresholds; equality is accepted and malformed strings are rejected. No graph restriction is imposed.
This complements the hardness results: together with Theorems 1 and 2 it places both oracles between and .
Formalization Note Meiburg's comparison theorem, on which the paper's proof relies, is not a hypothesis; it is part of what a proof must supply.
Differences from the source:
- encoding: P^{NP^{PP}} → ∃ A ∈ PP (no oracle), B ∈ NP^A with L ∈ P^B, on the published finite oracle machines; reason: the paper's 'deterministic polynomial time with an NP^{PP} oracle'
- encoding: counting hierarchy → the published InCountingHierarchy (C_0P = P, C_{j+1}P = PP^{C_jP}); reason: the paper's definition on p.23
- encoding: Cover-Time and Max-Cover-Time inputs → the published specified-start language and the start-free maxLanguage over bit strings; reason: same graphs and thresholds; malformed strings rejected
Preamble
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_MaxCover import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_OracleClasses
Formal statement
namespace CoverTime537.SpecifiedStart.Supplement
/-- Aghazadeh, STOC 2027 submission #537, Theorem 3, p.3.
Cover-Time and Max-Cover-Time (general valid graphs, all signed rational
thresholds, equality included, malformed strings rejected) are in `P^{NP^{PP}}`
and in the counting hierarchy. -/
theorem theorem_3 :
(InPNPPP CoverTime537.SpecifiedStart.language ∧
APSCounting893.Main.InCountingHierarchy CoverTime537.SpecifiedStart.language) ∧
(InPNPPP maxLanguage ∧ APSCounting893.Main.InCountingHierarchy maxLanguage) := by sorry
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, Theorem 3 p.3; proof Appendix C pp.22–23