A Topological Obstruction to Shallow Boolean Circuits

This paper introduces a topological framework for studying lower bounds in Boolean circuit complexity. To each Boolean language, a canonical simplicial complex is associated, encoding literal compatibility across accepting assignments. It is shown that any family of Boolean circuits of constant depth and polynomial size induces simplicial complexes that are collapsible to dimension one, and therefore have trivial second homology. Explicit CNF formulas are then exhibited whose associated complexes have nontrivial second homology, yielding a topological obstruction to constant-depth circuit computation. Finally, a conjectural extension to logarithmic-depth circuits (NC1) is formulated as an independent open problem, and the intrinsic limitations of the method are explicitly delineated.