Computational complexity of threshold automata networks under different updating schemes
Publication:475388
DOI10.1016/J.TCS.2014.09.010zbMath1360.68557OpenAlexW2065909799MaRDI QIDQ475388
Pedro Montealegre, Eric Goles Chacc
Publication date: 26 November 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.010
computational complexitythreshold functionsNP-hardnessNCP-completenessautomata networksupdating scheme
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (12)
Cites Work
- The complexity of the bootstraping percolation and other problems
- An introduction to sequential dynamical systems
- Decreasing energy functions as a tool for studying threshold networks
- On efficient parallel strong orientation
- Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
- No polynomial bound for the period of the parallel chip firing game on graphs
- Computational Complexity
- Neural networks and physical systems with emergent collective computational abilities.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Computational complexity of threshold automata networks under different updating schemes