Real p-families and monotone formula and branching-program classes
DefinitionMonoABPWidth_Hierarchy_Supplement_familiesA polynomial family supplies a finite number of variables and a real polynomial in those variables. It is a p-family when and are polynomially bounded. A polynomial bound has the uniform form
with fixed natural . Constants and exponents can depend on fixed theorem parameters, but not on .
Membership in means that actual monotone trees computing have polynomial total gate count. Membership in additionally requires alternating trees of total depth at most . Membership in means that the published affine-label mABPs computing have width at most and polynomial vertex count, where vertex count sums all layer sizes. All three classes include the p-family requirements. They are nonuniform: the definitions impose no algorithm for choosing the trees or programs.
The threshold for Theorem 6.4 is . Its ordinary real-logarithm values at small indices have no effect on eventual little-o assertions. Renaming any finite variable set into preserves these classes.
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_formulas
import Definitions.Def_MonoABPWidth_Hierarchy_branchingProgram
open scoped BigOperators ENNReal
namespace MonoABPWidth.Hierarchy.Supplement
/-- A uniform polynomial bound, with finite exceptions absorbed by C. -/
def PolynomiallyBounded (s : ℕ → ℕ) : Prop :=
∃ C a : ℕ, ∀ t : ℕ, s t ≤ C * (t + 1) ^ a
/-- Generic real polynomial families, before imposing resource or p-family bounds.
Every finite variable set can be renamed into Fin(nvars t). -/
structure PolynomialFamily where
nvars : ℕ → ℕ
poly : (t : ℕ) → MvPolynomial (Fin (nvars t)) ℝ
def PolynomialFamily.IsPFamily (f : PolynomialFamily) : Prop :=
PolynomiallyBounded f.nvars ∧ PolynomiallyBounded (fun t => (f.poly t).totalDegree)
/-- Nonuniform polynomial gate count; no bound on depth. -/
def InMVF (f : PolynomialFamily) : Prop :=
f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
∃ F : Formula (Fin (f.nvars t)), F.eval = f.poly t ∧ F.size ≤ C * (t + 1) ^ a
/-- Bounded total depth, with the alternating convention of §2.3. -/
def InMVFDepth (D : ℕ) (f : PolynomialFamily) : Prop :=
f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
∃ F : Formula (Fin (f.nvars t)), F.eval = f.poly t ∧
F.Alternating ∧ F.depth ≤ D ∧ F.size ≤ C * (t + 1) ^ a
/-- The source's vertex count, including both singleton endpoint layers. -/
def vertexCount {σ : Type} (A : MABP σ) : ℕ := ∑ i, A.layerSize i
/-- Full affine-label mABPs, polynomial vertex count and pointwise width bound. -/
def InMVBP (W : ℕ → ℕ) (f : PolynomialFamily) : Prop :=
f.IsPFamily ∧ ∃ C a : ℕ, ∀ t : ℕ,
∃ A : MABP (Fin (f.nvars t)), A.output = f.poly t ∧
A.width ≤ W t ∧ vertexCount A ≤ C * (t + 1) ^ a
/-- All logarithms in the width threshold of Theorem 6.4 are base two. -/
noncomputable def widthThreshold (t : ℕ) : ℝ :=
Real.logb 2 (t : ℝ) / (Real.logb 2 (Real.logb 2 (t : ℝ))) ^ 2
end MonoABPWidth.Hierarchy.Supplement