On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules

Abstract : We study how hard is to determine some fundamental properties of dynamics of certain types of network automata. We address the computational complexity of determining how many different possible dynamic evolutions can arise from some structurally very simple, deterministic and sparsely connected network automata. In this as well as our prior, related work, we try to push the limits on the underlying simplicity of two structural aspects of such network automata: (i) the uniform sparseness of their topologies, and (ii) severely restricted local behaviors of the individual agents (that is, the local update rules of the network nodes). In this endeavor, we prove that counting the Fixed Point (FP) configurations and the predecessor and ancestor configurations in two classes of network automata, called Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively), are computationally intractable problems. Moreover, this intractability is shown to hold when each node in such a network is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. Furthermore, the hardness of the exact enumeration of FPs and other types of configurations of interest remains to hold even in some severely restricted cases with respect to both the network topology and the diversity (or lack thereof) of individual node's local update rules. Namely, we show that the counting problems of interest remain hard even when the nodes of an SDS or SyDS use at most two different update rules from a given restricted class, and, additionally, when the network topologies are constrained so that each node has only $c = O(1)$ neighbors for small values of constant $c$. Our results also have considerable implications for other discrete dynamical system models studied in applied mathematics, physics, biology and computer science, such as Hopfield networks and spin glasses. In particular, one corollary of our results is that determining the memory capacity of sparse discrete Hopfield networks (viewed as associative memories) remains computationally intractable even when the interconnection and dependence structure among the nodes of a Hopfield network is severely restricted.
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.125-144, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [69 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185493
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:29
Dernière modification le : mardi 7 mars 2017 - 15:06:52
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:02:02

Fichier

dmAL0109.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185493, version 1

Collections

Citation

Predrag T. Tošić. On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.125-144, 2010, DMTCS Proceedings. 〈hal-01185493〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

214