circuit_lower_bound_topological
plain-language theorem explainer
Researchers establishing exponential circuit lower bounds for SAT would cite this result: under the topological obstruction hypothesis, any circuit deciding an unsatisfiable CNF formula on n variables has gate count at least 2 to the power n/k for some positive integer k. The module positions this as the core of the P versus NP argument via J-frustration barriers in the cost landscape. The proof is a direct one-line application of the exponential_lower_bound field inside the hypothesis structure.
Claim. Assuming the topological obstruction hypothesis holds, for any natural number $n$, any CNF formula $f$ on $n$ variables that is unsatisfiable, and any Boolean circuit $c$ on $n$ variables that decides $f$, there exists a positive integer $k$ such that the gate count of $c$ satisfies $c.gate_count >= 2^{n/k}$.
background
The module formalizes circuit lower bounds from J-frustration, where the Recognition Composition Law endows the J-cost landscape with multiplicative structure that polynomial circuits cannot exploit. TopologicalObstructionHyp is the structure whose exponential_lower_bound field asserts that for UNSAT formulas the defect moat (J-cost >=1 everywhere) creates a barrier any deciding circuit must encode. BooleanCircuit is a feed-forward structure with gate_count and gates in topological order; CircuitDecides asserts existence of an evaluation matching the formula's satisfiedBy predicate on all assignments.
proof idea
The proof is a one-line wrapper that applies the exponential_lower_bound component of the TopologicalObstructionHyp hypothesis directly to the parameters n, f, hunsat, c, and hdec.
why it matters
This theorem supplies the topological exponential lower bound to the circuitLowerBoundCert definition, completing one branch of the P ≠ NP implication. It instantiates the depth-width tradeoff for high J-frustration formulas as described in the module overview, linking J-cost barriers to circuit complexity in the Recognition Science program.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.