A Complete Complexity Dichotomy for Cyclic Attractor Detection in Boolean Networks with Restricted Local Rules

Abstract

Boolean networks (BNs) are finite models of interacting systems whose long-term behaviour is organised by attractors. After a transient phase, every synchronously updated BN reaches either a fixed state or a cyclic attractor. Therefore, deciding whether a prescribed cyclic behaviour exists is a basic computational task in finite-state network dynamics. Here we study this task for networks with restricted local rules: each node is updated by a Boolean rule from a fixed closed rule family, and the period is fixed in advance. We prove a complete dichotomy for every fixed period at least two. For each closed rule family, cyclic-attractor detection is either polynomial-time decidable or $\mathrm{NP}$-complete. The intractable cases are precisely those that can implement majority-like self-dual behaviour or mixed monotone conjunction-disjunction mechanisms. In the tractable cases, affine, purely conjunctive, or purely disjunctive structure reduces the problem to linear algebra or graph reachability. These criteria identify which restricted local rule families preserve computational tractability in finite Boolean network models.

24 pages, 3 figures, 3 tables