Max-Cover-Time language and maximum-start #P oracle reductions
DefinitionCoverTime537_SpecifiedStart_Supplement_MaxCoverFor a finite simple graph with at least one vertex, the maximum expected cover time is
where is the published full-cover expectation of the ordinary uniform-neighbor walk started at , 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 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
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 in binary, whose single-bit oracle answers decide . #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 , which they use only via .
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