A Parsimonious Reduction from #SAT to Motif-Avoidant Attractors in Bounded-Fan-In AND-NOT Boolean Networks

We present an explicit polynomial-time parsimonious reduction from #SAT to counting motif-avoidant attractors of asynchronous Boolean networks. Every update function is a constant or a conjunction of at most two signed literals, and the interaction graph has exactly one nontrivial strongly connected component consisting of two vertices. For every CNF formula φ, the constructed network satisfies #MAA(Nφ) = #SAT(φ). The proof classifies both terminal state-transition strongly connected components and minimal trap subcubes, establishing #P-hardness of counting motif-avoidant attractors and NP-hardness of deciding their existence within this restricted network class. Independent exact finite-state implementations check the construction on representative small formulas. The accompanying source archive includes the LaTeX manuscript, verification code, logs and checksums.