Documentation

Complexitylib.Circuits.Internal.ShannonBridge

Internal: Shannon bridge from descriptors to typed circuits #

This module pads the descriptor of a typed single-output circuit to the fixed size used by the Shannon counting argument and transfers the resulting lower bound back to Circuit.

theorem Complexity.shannon_lower_bound_circuit_internal (N : ) [NeZero N] (hN : 6 N) :
∃ (f : BitString NBool), ∀ (G : ) (c : Circuit Basis.andOr2 N 1 G), G + 1 2 ^ N / (5 * N) → (fun (x : BitString N) => c.eval x 0) f

Internal Shannon lower bound transported to typed circuits.