Majority Boolean networks classifying density: structural characterization and complexity
Abstract
Given a set of entities each holding a Boolean state, the Density Classification Task (DCT) asks them to converge to the most represented state. Given a directed graph of entities where each node synchronously updates to the local majority among its in-neighbors, we characterize in terms of three forbidden patterns when it solves DCT, and show that discovering these patterns is complete for NP and PSPACE.
Fields of Study & Subjects
Cellular Automata and Applications
semigroups and automata theory
DNA and Biological Computing
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 13 February 2026
- Language
- EN
- Document type
- Preprint