Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Max-Cover-Time language and maximum-start #P oracle reductions

Definition
CoverTime537_SpecifiedStart_Supplement_MaxCover

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For a finite simple graph HHH with at least one vertex, the maximum expected cover time is

M(H)=max⁡s∈V(H)CH(s),M(H)=\max_{s\in V(H)} C_H(s),M(H)=s∈V(H)max​CH​(s),

where CH(s)C_H(s)CH​(s) is the published full-cover expectation of the ordinary uniform-neighbor walk started at sss, with the start visited at time zero.

An input of Max-Cover-Time consists of a vertex count, neighbor lists and a signed binary rational threshold rrr with positive denominator, in the same self-delimiting encoding as the published Cover-Time language but without a start field. Validity is the published validity: positive vertex count, one list per vertex, distinct in-range neighbors, no self-loops, symmetric incidence and a connected graph. A bit string belongs to the language exactly when it encodes a valid input with

M(H)≤r.M(H)\le r .M(H)≤r.

Equality answers yes; malformed strings answer no. The restricted query class is the published one: a common universal hub, a distinct nonadjacent pair (diameter exactly two), degree at most five at each non-hub vertex, and planar bipartite hub deletion.

The oracle reduction notion is the published one, with the oracle replaced: a fixed finite-alphabet multitape oracle machine with input-independent polynomial bounds on its steps and query lengths, outputting f(x)f(x)f(x) in binary, whose single-bit oracle answers decide M(H)≤rM(H)\le rM(H)≤r. #P-hardness of Max-Cover-Time means that every ordinary #P function (published polynomial-time certificate counting) has such a reduction; in the restricted version every query is a valid restricted encoding.

These objects state Theorem 2 of the paper and the Max-Cover-Time half of Theorem 3.

Formalization Note The reduction predicate is the published Reduces with the oracle and the query class as parameters; at the specified-start oracle it is the published Reduces by definition. The start-free query reuses the published graph, validity and restriction predicates through a start label 000, which they use only via 0<n0<n0<n.

Definition code
import Mathlib
import Definitions.Def_CoverTime537_SpecifiedStart_Complexity

namespace CoverTime537.SpecifiedStart.Supplement
noncomputable section
open scoped BigOperators
open CoverTime537.SpecifiedStart

/-- Source eq. (2), p.2: `M(H) = max_s C_H(s)`, the maximum of the published
specified-start cover expectation over the (finite, nonempty) vertex set.
`Finset.sup'` needs nonemptiness, so no empty-maximum default occurs. -/
def maxCover {V : Type} [Fintype V] [DecidableEq V] [Nonempty V]
    (H : SimpleGraph V) : ℝ :=
  Finset.univ.sup' Finset.univ_nonempty (fun x => cover H x)

/-- Max-Cover-Time input: the same neighbor-list graph and threshold as the
published `Query`, without a start field. -/
structure MaxQuery where
  n : ℕ
  neighbors : List (List ℕ)
  threshold : Threshold

/-- The published query with the same graph and threshold; its start label `0`
is used only to reuse the published graph, validity and restriction predicates,
none of which depends on the start except through `0 < n`. -/
def MaxQuery.toQuery (q : MaxQuery) : Query :=
  ⟨q.n, q.neighbors, 0, q.threshold⟩

def MaxQuery.graph (q : MaxQuery) : SimpleGraph (Fin q.n) := q.toQuery.graph

/-- Exactly the published `Query.Valid` minus the start condition (the start
condition `0 < n` coincides with the vertex-count condition `0 < n`). -/
def MaxQuery.Valid (q : MaxQuery) : Prop := q.toQuery.Valid

/-- Exactly the published restricted class: one common universal hub, a distinct
nonadjacent pair, non-hub degree at most five, planar and bipartite hub deletion. -/
def MaxQuery.Restricted (q : MaxQuery) : Prop := q.toQuery.Restricted

/-- Same self-delimiting encoding as the published `Query.encode`, with no start field. -/
def MaxQuery.encode (q : MaxQuery) : List Bool :=
  binaryNat q.n ++ (q.neighbors.map binaryList).flatten ++ q.threshold.encode

/-- Max-Cover-Time (source eq. (2)): valid parsed tuples with `M(H) ≤ r`.
Equality is yes; malformed strings are no. -/
def maxLanguage (bits : List Bool) : Prop :=
  ∃ q : MaxQuery, q.Valid ∧ q.encode = bits ∧
    ∃ hn : 0 < q.n,
      @maxCover (Fin q.n) _ _ ⟨⟨0, hn⟩⟩ q.graph ≤ (q.threshold.value : ℝ)

def validRestrictedMaxQuery (bits : List Bool) : Prop :=
  ∃ q : MaxQuery, q.Restricted ∧ q.encode = bits

/-- The Max-Cover-Time decision oracle: one bit, yes at equality. -/
def maxAnswer (bits : List Bool) : List Bool := by
  classical
  exact [decide (maxLanguage bits)]

/-- The published `Reduces`, verbatim, with the oracle `ans` and the restricted
query predicate `validQ` as parameters. `ReducesWith answer validRestrictedQuery`
is the published `Reduces`. -/
def ReducesWith (ans : List Bool → List Bool) (validQ : List Bool → Prop)
    (f : List Bool → ℕ) (restricted : Bool) : Prop :=
  ∃ (O : OracleMachine) (c d : ℕ), O.WF ∧
    O.ComputesInTime ans (CookLevin.polyBound c d) (fun x => binaryNat (f x)) ∧
    ∀ x t, t < CookLevin.polyBound c d x.length →
      let cfg := O.run ans (CookLevin.polyBound c d x.length + 2)
        (CookLevin.startConfig2 O.k (CookLevin.boolsToSymbols x) []) t
      cfg.1 = O.qState →
        let q := CookLevin.readBits (CookLevin.polyBound c d x.length + 2)
          (CookLevin.tapeFun cfg O.qTape) 1
        q.length ≤ CookLevin.polyBound c d x.length ∧
          (restricted = true → validQ q)

/-- Ordinary exact #P hardness for the maximum-start oracle: every published
`InSharpP` function is computed in binary by one polynomial-time oracle machine
answering queries by `M(H) ≤ r`; in the restricted version every query is a
valid restricted start-free encoding. -/
def SharpPHardMax (restricted : Bool) : Prop :=
  ∀ f : List Bool → ℕ, InSharpP f →
    ReducesWith maxAnswer validRestrictedMaxQuery f restricted

end
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, §1 p.2 eq. (2) and the sentence 'The maximum-start language has the same graph and threshold encoding'; Theorem 2 p.2

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me