Theorem 5.10 — fixed-depth formula separation
OpenMonoABPWidth.Hierarchy.Supplement.theorem_5_10algebraic-complexitymonotone-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every integer , there is a real p-family with polynomial-size monotone formulas of total depth at most , but no polynomial-size monotone branching programs of width at most :
The family may depend on . The statement includes and compares the full nonuniform classes, with polynomial variable count and degree. It is a companion separation theorem.
Differences from the source:
- encoding: noninclusion of p-family classes → existence of a PolynomialFamily in InMVFDepth (2*k) and outside InMVBP (k-1); reason: class definitions include p-family bounds, actual computations, and uniform polynomial resource constants; finite renaming loses no families
Preamble
import Definitions.Def_MonoABPWidth_Hierarchy_Supplement_families open scoped BigOperators ENNReal
Formal statement
namespace MonoABPWidth.Hierarchy.Supplement
/-- Theorem 5.10, p.15 (PDF16), including k=2 and k=3. -/
theorem theorem_5_10 (k : ℕ) (hk : 2 ≤ k) :
∃ f : PolynomialFamily, InMVFDepth (2 * k) f ∧
¬ InMVBP (fun _ => k - 1) f := by sorry
end MonoABPWidth.Hierarchy.Supplement
Source
Julian Dörfler, Alexander Rogovskyy, STOC 2027 submission #927 (October 2026), Theorem 5.10, p.15, PDF16