On computational complexity of counting fixed points in symmetric boolean graph automata

Predrag T. Tošić, Gui A. Agha

Research output: Contribution to journalConference article

Abstract

We study computational complexity of counting the fixed point configurations (FPs) in certain classes of graph automata viewed as discrete dynamical systems. We prove that both exact and approximate counting of FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the problems of counting exactly the garden of Eden configurations (GEs), as well as all transient configurations, are in general intractable, as well. Moreover, exactly enumerating FPs or GEs remains hard even in some severely restricted cases, such as when the nodes of an SDS or SyDS use only two different symmetric Boolean update rules, and every node has a neighborhood size bounded by a small constant.

Original languageEnglish (US)
Pages (from-to)191-205
Number of pages15
JournalLecture Notes in Computer Science
Volume3699
StatePublished - Oct 31 2005
Event4th International Conference on Unconventional Computation, UC 2005 - Sevilla, Spain
Duration: Oct 3 2005Oct 7 2005

Fingerprint

Automata
Counting
Computational complexity
Dynamical systems
Computational Complexity
Fixed point
Configuration
Boolean functions
Graph in graph theory
Vertex of a graph
Update
Discrete Dynamical Systems
Symmetric Functions
Boolean Functions
Dynamical system
Class

Keywords

  • #P-completeness
  • Cellular and graph automata
  • Computational complexity
  • Configuration space properties
  • Sequential and synchronous dynamical systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

On computational complexity of counting fixed points in symmetric boolean graph automata. / Tošić, Predrag T.; Agha, Gui A.

In: Lecture Notes in Computer Science, Vol. 3699, 31.10.2005, p. 191-205.

Research output: Contribution to journalConference article

@article{78ae70302cb9426b908a9dbc6f1c2b6d,
title = "On computational complexity of counting fixed points in symmetric boolean graph automata",
abstract = "We study computational complexity of counting the fixed point configurations (FPs) in certain classes of graph automata viewed as discrete dynamical systems. We prove that both exact and approximate counting of FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the problems of counting exactly the garden of Eden configurations (GEs), as well as all transient configurations, are in general intractable, as well. Moreover, exactly enumerating FPs or GEs remains hard even in some severely restricted cases, such as when the nodes of an SDS or SyDS use only two different symmetric Boolean update rules, and every node has a neighborhood size bounded by a small constant.",
keywords = "#P-completeness, Cellular and graph automata, Computational complexity, Configuration space properties, Sequential and synchronous dynamical systems",
author = "Tošić, {Predrag T.} and Agha, {Gui A.}",
year = "2005",
month = "10",
day = "31",
language = "English (US)",
volume = "3699",
pages = "191--205",
journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - On computational complexity of counting fixed points in symmetric boolean graph automata

AU - Tošić, Predrag T.

AU - Agha, Gui A.

PY - 2005/10/31

Y1 - 2005/10/31

N2 - We study computational complexity of counting the fixed point configurations (FPs) in certain classes of graph automata viewed as discrete dynamical systems. We prove that both exact and approximate counting of FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the problems of counting exactly the garden of Eden configurations (GEs), as well as all transient configurations, are in general intractable, as well. Moreover, exactly enumerating FPs or GEs remains hard even in some severely restricted cases, such as when the nodes of an SDS or SyDS use only two different symmetric Boolean update rules, and every node has a neighborhood size bounded by a small constant.

AB - We study computational complexity of counting the fixed point configurations (FPs) in certain classes of graph automata viewed as discrete dynamical systems. We prove that both exact and approximate counting of FPs in Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively) are computationally intractable, even when each node is required to update according to a symmetric Boolean function. We also show that the problems of counting exactly the garden of Eden configurations (GEs), as well as all transient configurations, are in general intractable, as well. Moreover, exactly enumerating FPs or GEs remains hard even in some severely restricted cases, such as when the nodes of an SDS or SyDS use only two different symmetric Boolean update rules, and every node has a neighborhood size bounded by a small constant.

KW - #P-completeness

KW - Cellular and graph automata

KW - Computational complexity

KW - Configuration space properties

KW - Sequential and synchronous dynamical systems

UR - http://www.scopus.com/inward/record.url?scp=27144560195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=27144560195&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:27144560195

VL - 3699

SP - 191

EP - 205

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SN - 0302-9743

ER -