Literals and constants
DefinitionAvgPHETH_Supplement_Litcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
A leaf label over a set of Boolean variables is either a literal, or for , or a constant or . Leaves of alternating formulas and input vertices of alternating circuits carry such labels.
Definition code
import Mathlib namespace AvgPHETH.Supplement /-- A leaf label of an alternating formula or an input vertex of an alternating circuit: a literal (`var x true` is `x`, `var x false` is `¬x`) or a constant (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): "leaves are labelled by literals or constants"; "Input vertices are labeled by literals or constants"). -/ inductive Lit (V : Type) where | var : V → Bool → Lit V | const : Bool → Lit 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)