AND-OR formulas
DefinitionAvgPHETH_Supplement_Formulacircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
An AND-OR formula over variables is a finite tree whose leaves are labelled by literals or constants and whose internal nodes are AND gates or OR gates, each with a finite ordered list of children. The alternation and layering conditions of §4.3 are imposed separately (Formula.IsLayeredAlt).
Definition code
import Mathlib import Definitions.Def_AvgPHETH_Supplement_Lit namespace AvgPHETH.Supplement /-- An AND-OR formula: a tree whose internal nodes are AND gates (`gate true m ch`) or OR gates (`gate false m ch`) with `m` children `ch 0, …, ch (m-1)`, and whose leaves are labelled by literals or constants (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §4.3, p.16 (PDF 18)). Alternation and layering are the separate predicate `Formula.IsLayeredAlt`. -/ inductive Formula (V : Type) where | leaf : Lit V → Formula V | gate : Bool → (m : ℕ) → (Fin m → Formula V) → Formula V end AvgPHETH.Supplement
Source
Hirahara–Juvekar–Nanashima, Average-Case Hardness of PH from ETH-Type Hypotheses, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §4.3, p.16 (PDF 18)