Portal de Periódicos da CAPES

DICHOTOMY RESULTS FOR FIXED POINT COUNTING IN BOOLEAN DYNAMICAL SYSTEMS

2007; Elsevier BV; Linguagem: Inglês

10.1142/9789812770998_0018

1879-2294

Sven Kosub, Christopher M. Homan,

Complexity and Algorithms in Graphs

Theoretical Computer Science, pp. 163-174 (2007) No AccessDICHOTOMY RESULTS FOR FIXED POINT COUNTING IN BOOLEAN DYNAMICAL SYSTEMSSVEN KOSUB and CHRISTOPHER M. HOMANSVEN KOSUBFakultät für Informatik, Technische Universität München, D-85748 Garching, Germany and CHRISTOPHER M. HOMANDepartment of Computer Science, Rochester Institute of Technology, Rochester, NY 14623, USAhttps://doi.org/10.1142/9789812770998_0018Cited by:7 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}. For a class of boolean functions and a class of graphs, an -system is a boolean dynamical system with local transitions functions lying in and graph in . We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let be a class of boolean functions closed under superposition and let be a graph class closed under taking minors. If contains all min-functions, all max-functions, or all self-dual and monotone functions, and contains all planar graphs, then it is #P-complete to compute the number of fixed points in an -system; otherwise it is computable in polynomial time. The theorem relies on an evident conjecture for an open case. In contrast, we prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). A corresponding theorem for boolean circuits coincides with the theorem for formulas. FiguresReferencesRelatedDetailsCited By 7Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR FunctionsM. Ogihara and K. Uchizawa10 December 2022 | Theory of Computing Systems, Vol. 295Agent-Based Computational Epidemiological ModelingKeith R. Bissett, Jose Cadena, Maleq Khan and Chris J. Kuhlman5 October 2021 | Journal of the Indian Institute of Science, Vol. 101, No. 3Evolution of Similar Configurations in Graph Dynamical SystemsJoshua D. Priest, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz and Richard E. Stearns20 December 2020Graphical dynamical systems and their applications to bio-social systemsAbhijin Adiga, Chris J. Kuhlman, Madhav V. Marathe, Henning S. Mortveit and S. S. Ravi et al.15 December 2018 | International Journal of Advances in Engineering Sciences and Applied Mathematics, Vol. 11, No. 2Computational Complexity Studies of Synchronous Boolean Finite Dynamical SystemsMitsunori Ogihara and Kei Uchizawa16 April 2015Complexity of Inferring Local Transition Functions of Discrete Dynamical SystemsAbhijin Adiga, Chris J. Kuhlman, Madhav V. Marathe, S. S. Ravi and Daniel J. Rosenkrantz et al.28 July 2015Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systemsChris Barrett, Harry B. Hunt, Madhav V. Marathe, S.S. Ravi and Daniel J. Rosenkrantz et al.1 Jul 2011 | Theoretical Computer Science, Vol. 412, No. 30 Theoretical Computer ScienceMetrics History PDF download