Hamiltonian Route: Separator Interface States and the Anti-Stitch Framework

We prove that every Boolean fan-in-2 circuit computing the Hamiltonian Cycle function HAMₙ on n vertices has size 2^Ω (n). The previous best lower bounds for explicit functions in NP were polynomial: Ω (n^3-o (1) ) for formulas (Håstad Hastad98) and Ω (n^2. 5-o (1) ) via the Andreev function framework Andreev87. Our proof combines three ingredients: (i) a separator-interface stitchability theory for Hamiltonian cycles, exploiting the shared vertex set to avoid the isolation pathology that kills the CLIQUE route; (ii) a multi-carrier funnel: a recursive magnification scheme maintaining q = (log n) ^O (1) bichromatic carrier edges throughout the recursion, where each step extends every carrier to a degree-visible switch block, branches on all 2q local-state patterns, and suppresses the internal vertices—consuming the old carriers and replacing them with new ones of the same restriction cost, so the background restriction mass stays constant across the entire recursion depth, yielding an unconditional 2^Ω (n) formula lower bound; (iii) a legal monotone lift with continuation-packet sharing control, extended to general circuits via a rooted-packet descent argument that eliminates non-terminal packet-separating first escapes at height ≥1 and absorbs the unique terminal escape at height 0 into the occurrence-signature multiplicity bound.