Deterministic layered oracle branching programs
DefinitionCompressedOracleDuality_LabelSymmetric_Supplement_LayeredProgramLet be a natural number and let be the query, answer, and output types. A deterministic layered oracle branching program has finite vertex sets , a singleton initial layer , a query and a total transition for each , and a leaf-output map . Distinct edges may merge; queries may be adaptive or repeated. For an oracle its actual execution is
The -bit space predicate is only for . There is no numerical bound on the finite terminal layer. The source's exact internal width is recovered by padding unreachable vertices. At the initial and terminal layer is the same singleton and the output is fixed.
This general query-program object is separate from the collision-specific alphabet, symmetry, and success definitions. It imposes no reversibility, success requirement, or matched-label bound.
import Mathlib
namespace CompressedOracleDuality.LabelSymmetric.Supplement
/-- Definition 5.4, p.27: a deterministic layered oracle branching program.
`X`, `Y`, and `O` are the query, answer, and output types. Distinct edges may merge.
No width condition is built into the general object. -/
structure LayeredProgram (X Y O : Type) (T : ℕ) where
Vertex : Fin (T + 1) → Type
finite : ∀ t, Fintype (Vertex t)
initial : Unique (Vertex 0)
query : (t : Fin T) → Vertex t.castSucc → X
step : (t : Fin T) → Vertex t.castSucc → Y → Vertex t.succ
output : Vertex (Fin.last T) → O
attribute [instance] LayeredProgram.finite
/-- Actual execution: the next vertex depends only on the current vertex and query answer. -/
def LayeredProgram.run {X Y O : Type} {T : ℕ}
(B : LayeredProgram X Y O T) (H : X → Y) : (t : Fin (T + 1)) → B.Vertex t :=
Fin.induction B.initial.default (fun t m => B.step t m (H (B.query t m)))
/-- Definition 5.4: only layers 1,...,T-1 count against the S-bit width bound.
The source's exact width is recovered by padding unreachable internal vertices. -/
def LayeredProgram.SpaceBound {X Y O : Type} {T : ℕ}
(B : LayeredProgram X Y O T) (S : ℕ) : Prop :=
∀ t : Fin (T + 1), 0 < t.val → t.val < T → Fintype.card (B.Vertex t) ≤ 2 ^ S
end CompressedOracleDuality.LabelSymmetric.Supplement