Theorem 2 — #P-hardness of Max-Cover-Time
OpenCoverTime537.SpecifiedStart.Supplement.theorem_2The exact comparison language , with , is #P-hard under deterministic polynomial-time Turing reductions:
The hardness holds even with every oracle query a valid neighbor-list encoding of a connected simple undirected unweighted graph with a common universal hub, diameter exactly two, degree at most five at each non-hub vertex, and planar bipartite hub deletion. Thresholds are arbitrary signed binary rationals with positive denominator; equality answers yes and malformed encodings answer no. Unrestricted hardness is stated as well.
Each reduction is one fixed finite machine with polynomial bounds on its steps and query lengths, independent of the input, and outputs the #P count in binary. Euler-tour counting hardness, cover-time bounds, the value of and decoder correctness are not hypotheses.
This is the maximum-start companion of the mission's goal (Theorem 1).
Differences from the source:
- encoding: graphs by neighbor lists and binary rational thresholds, no start → self-delimiting binary vertex count, raw neighbor lists and signed rational fields, with no start field; reason: every source instance is represented; invalid encodings are rejected
- encoding: #P hardness under polynomial-time Turing reductions → exact polynomial-time binary-certificate counts and finite-alphabet oracle-machine execution with the Max-Cover-Time oracle; reason: the published machine model of the goal, with only the oracle changed
- encoding: universal hub and diameter two → universal hub and a distinct nonadjacent pair; reason: equivalent to diameter exactly two for a graph with a universal hub
- encoding: maximum of expected cover times → Finset.sup' over the nonempty vertex set of the published tail-sum cover expectation; reason: valid inputs have at least one vertex; no empty-maximum default
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_MaxCover
namespace CoverTime537.SpecifiedStart.Supplement /-- Aghazadeh, STOC 2027 submission #537, Theorem 2, p.2. Unconditional ordinary exact #P function hardness of Max-Cover-Time. All queries of the restricted reduction satisfy ALL graph conditions for a common hub; equality answers yes. -/ theorem theorem_2 : SharpPHardMax true ∧ SharpPHardMax false := by sorry end CoverTime537.SpecifiedStart.Supplement