pith. machine review for the scientific record. sign in
structure definition def or abbrev

CircuitLowerBoundCert

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

 239structure CircuitLowerBoundCert where
 240  /-- Algebraic restriction gives linear lower bound -/
 241  algebraic_linear : AlgebraicRestrictionHyp →
 242    ∀ (n : ℕ) (f : CNFFormula n), f.isUNSAT →
 243    ∀ (c : BooleanCircuit n), CircuitDecides c f →
 244    (c.gate_count : ℝ) ≥ n
 245  /-- Topological obstruction gives exponential lower bound -/
 246  topological_exp : TopologicalObstructionHyp →
 247    ∀ (n : ℕ) (f : CNFFormula n), f.isUNSAT →
 248    ∀ (c : BooleanCircuit n), CircuitDecides c f →
 249    ∃ (k : ℕ), 0 < k ∧ (c.gate_count : ℝ) ≥ 2 ^ (n / k)
 250

used by (3)

From the project-wide theorem graph. These declarations reference this one in their body.

depends on (5)

Lean names referenced from this declaration's body.