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

CircuitZCapacity

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)

 154def CircuitZCapacity {n : ℕ} (c : BooleanCircuit n) : ℕ :=

proof body

Definition body.

 155  CircuitBondCount c
 156
 157/-- **THEOREM (Circuit Capacity Bound).**
 158    A Boolean circuit of size S has Z-complexity capacity at most 2S.
 159
 160    The significance: a polynomial-size circuit (S = poly(n)) has
 161    Z-capacity at most 2·poly(n) = poly(n). -/

used by (4)

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

depends on (15)

Lean names referenced from this declaration's body.