pith. machine review for the scientific record. sign in
theorem proved tactic proof

poly_circuit_poly_capacity

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)

 167theorem poly_circuit_poly_capacity {n : ℕ} (c : BooleanCircuit n)
 168    (h_poly : ∃ (k d : ℕ), c.gate_count ≤ k * n ^ d) :
 169    ∃ (k d : ℕ), CircuitZCapacity c ≤ k * n ^ d := by

proof body

Tactic-mode proof.

 170  obtain ⟨k, d, hk⟩ := h_poly
 171  exact ⟨2 * k, d, by
 172    calc CircuitZCapacity c ≤ 2 * c.gate_count := circuit_capacity_bound c
 173      _ ≤ 2 * (k * n ^ d) := by linarith
 174      _ = 2 * k * n ^ d := by ring⟩
 175
 176/-! ## Part 3: The Defect Moat -/
 177
 178/-- The **Defect Moat** for a formula f: 0 if SAT, 1 if UNSAT. -/

used by (1)

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.