Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438122 | Theoretical Computer Science | 2014 | 17 Pages |
Abstract
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND–OR rule (vertices take the And or the Or logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Eric Goles, Pedro Montealegre,