Encoded algorithms, randomized policies and probing sets for DVP
DefinitionDataValidation_Supplement_AlgorithmsA uniform encoded DVP algorithm is a multi-tape Turing machine in the published Cook–Levin step model. On the binary code of a DVP instance, a policy algorithm returns a nonempty finite uniform distribution of deterministic adaptive policy tables, while a set algorithm returns an edge set. The output policy tables are interpreted in the published DVP history semantics.
The module also defines valid policy-family output, expected reward, feasible deterministic probing sets, their weight, acyclic tournaments, uniform-cost/uniform-probability instances, and
with the total convention when the set is empty.
This substrate makes the algorithmic and running-time conclusions of Theorems 2–5 statements about actual encoded outputs rather than bare existence of optima.
Formalization Note A finite policy family is sampled uniformly before edge outcomes are revealed, so its random seed is independent of the Bernoulli probes. Every valid policy has at most probes, hence a finite reachable table. The all-zero-probability convention changes no optimum because every policy then has reward zero.
import Mathlib
import Definitions.Def_CookLevin_Cost
import Definitions.Def_DataValidation_Obtainable
import Definitions.Def_DataValidation_Policy
import Definitions.Def_DataValidation_value
import Definitions.Def_DataValidation_code
set_option autoImplicit false
namespace DataValidation.Supplement
/-- A finite table representing a deterministic adaptive policy. Histories not listed in the
table cause the policy to stop. This is the finite output object used by the encoded algorithms in
Theorems 3 and 4 of Tinguely--van der Heijden, arXiv:2611.06773 (sha256 6595f819...), p.2
(PDF p.3).
**Formalization Note.** A valid policy makes at most `|E|` probes, so only its finite table on
reachable histories matters. -/
structure FinitePolicy (I : Instance) where
table : List (I.History × Option I.Edge)
/-- Read the first matching row of a finite policy table. -/
def tableAction {I : Instance} :
List (I.History × Option I.Edge) → I.History → Option I.Edge
| [], _ => none
| (h', a) :: rows, h => if h = h' then a else tableAction rows h
/-- The adaptive policy represented by a finite table. -/
def FinitePolicy.toPolicy {I : Instance} (P : FinitePolicy I) : I.Policy :=
tableAction P.table
/-- A finite uniform distribution of deterministic policies. It represents all randomization used
by the algorithms in the paper: a random seed is sampled first and is independent of the edge
outcomes. The nonempty clause prevents division by zero. -/
structure PolicyFamily (I : Instance) where
policies : List (FinitePolicy I)
nonempty : policies ≠ []
/-- The expected reward of a uniformly sampled policy from a finite family. -/
noncomputable def PolicyFamily.reward {I : Instance} (P : PolicyFamily I) : ℝ :=
(P.policies.map fun Q => I.W Q.toPolicy).sum / P.policies.length
/-- Every policy in the output family is valid for the instance. -/
def PolicyFamily.IsValid {I : Instance} (P : PolicyFamily I) : Prop :=
∀ Q ∈ P.policies, I.IsValidPolicy Q.toPolicy
/-- A numerical encoding of one observed probing history. -/
def historyNumbers {I : Instance} (h : I.History) : List ℕ :=
h.flatMap fun x => [x.1.1.val, x.1.2.val, if x.2 then 1 else 0]
/-- A numerical encoding of the action `none` or `some (u,v)`. -/
def actionNumbers {I : Instance} : Option I.Edge → List ℕ
| none => [0]
| some e => [1, e.1.val, e.2.val]
/-- A self-delimiting binary code of one finite policy table. -/
def encodeFinitePolicy {I : Instance} (P : FinitePolicy I) : List Bool :=
CookLevin.encodeNat P.table.length ++
(P.table.map fun row =>
NPBinary.encodeList ([row.1.length] ++ historyNumbers row.1 ++ actionNumbers row.2)).flatten
/-- A self-delimiting binary code of a finite uniform policy family. -/
def encodePolicyFamily {I : Instance} (P : PolicyFamily I) : List Bool :=
CookLevin.encodeNat P.policies.length ++ (P.policies.map encodeFinitePolicy).flatten
/-- In the published Cook--Levin multi-tape model, `M` halts after `t` steps on input `x` with
the bit string `y` on its output tape. -/
def OutputsIn (M : CookLevin.Machine) (k : ℕ) (x y : List Bool) (t : ℕ) : Prop :=
let cfg := CookLevin.execute M (CookLevin.startConfig2 k (CookLevin.boolsToSymbols x) []) t
cfg.1 = M.length ∧ CookLevin.outputOf k cfg (t + 2) = y
/-- A uniform encoded DVP policy algorithm, with its actual Cook--Levin machine and step count.
The input is the published binary code of `(I,0)` and the output is a finite randomized policy.
This is the concrete machine/cost convention used for Theorems 2--4. -/
structure PolicyAlgorithm where
run : (I : Instance) → PolicyFamily I
time : Instance → ℕ
machine : CookLevin.Machine
tapes : ℕ
alphabet : ℕ
wf : CookLevin.TuringMachine tapes alphabet machine
computes : ∀ I, OutputsIn machine tapes (DataValidation.code I 0)
(encodePolicyFamily (run I)) (time I)
/-- The encoded instance conditions needed by the approximation algorithms, without the
transitivity condition in `Instance.IsValid`. The paragraph following Theorem 4 says that none
of the approximation algorithms requires `G` to be transitive, while the model continues to assume
that `G` is a DAG. The final clause is the published encoding's harmless normal form off `E`. -/
def IsDAGValid (I : Instance) : Prop :=
IsAcyclic I.E ∧
(∀ e ∈ I.E, 0 ≤ I.p e ∧ I.p e ≤ 1) ∧
(∀ e, e ∉ I.E → I.w e = 0 ∧ I.τ e = 0 ∧ I.p e = 0)
/-- `A` is a factor-`factor(I)` approximation on precisely the instance domain `C`. -/
def IsPolicyApproximationOn (A : PolicyAlgorithm) (factor : Instance → ℝ)
(C : Instance → Prop) : Prop :=
∀ I, 0 < I.T → C I →
1 ≤ factor I ∧ (A.run I).IsValid ∧ I.value ≤ factor I * (A.run I).reward
/-- `A` is a factor-`factor(I)` approximation on the class `C`: its output is a valid randomized
policy and its expected reward is at least `value(I)/factor(I)`. -/
def IsPolicyApproximation (A : PolicyAlgorithm) (factor : Instance → ℝ)
(C : Instance → Prop) : Prop :=
IsPolicyApproximationOn A factor (fun I => I.IsValid ∧ C I)
/-- Encode an edge set by its membership bit vector in the instance's lexicographically ordered
edge list. -/
def encodeEdgeSet (I : Instance) (R : Finset I.Edge) : List Bool :=
I.edgeList.map fun e => decide (e ∈ R)
/-- A uniform encoded algorithm returning an edge set. -/
structure SetAlgorithm where
run : (I : Instance) → Finset I.Edge
time : Instance → ℕ
machine : CookLevin.Machine
tapes : ℕ
alphabet : ℕ
wf : CookLevin.TuringMachine tapes alphabet machine
computes : ∀ I, OutputsIn machine tapes (DataValidation.code I 0)
(encodeEdgeSet I (run I)) (time I)
/-- A feasible deterministic probing set: obtainable and within the probing budget. -/
def FeasibleSet (I : Instance) (R : Finset I.Edge) : Prop :=
Obtainable I.E R ∧ ∑ e ∈ R, I.τ e ≤ I.T
/-- The total weight of a probing set. -/
def setWeight (I : Instance) (R : Finset I.Edge) : ℕ :=
∑ e ∈ R, I.w e
/-- The graph of the instance is a tournament: between every two distinct vertices at least one
orientation is present. Together with `Instance.IsValid`, acyclicity rules out both orientations and
the resulting tournament is the paper's total-order DAG. -/
def IsTournament (I : Instance) : Prop :=
∀ u v : Fin I.n, u ≠ v → (u, v) ∈ I.E ∨ (v, u) ∈ I.E
/-- The minimum strictly positive edge-success probability. When no edge has positive probability,
the value is defined to be `1`; the optimal reward is then zero, so this convention changes no
instance of Theorem 4 and avoids silently adding a nonemptiness hypothesis. -/
noncomputable def pmin (I : Instance) : ℝ :=
if ∃ e ∈ I.E, 0 < I.p e then
sInf {q : ℝ | ∃ e ∈ I.E, 0 < I.p e ∧ q = (I.p e : ℝ)}
else 1
/-- Uniform unit probing cost and fixed success probability `p`, the regime of Theorem 3. -/
def IsUniform (p : ℚ) (I : Instance) : Prop :=
∀ e ∈ I.E, I.τ e = 1 ∧ I.p e = p
/-- The two encoded algorithm interfaces used by the supplement: one returns randomized adaptive
policies and one returns deterministic probing sets. This declaration is the public entry point of
the definition module; the fields reuse all encoding and machine semantics above. -/
structure Algorithms where
policy : PolicyAlgorithm
set : SetAlgorithm
end DataValidation.Supplement