TY - JOUR
AU - Jang-Woo Park
AU - Shuhong Gao
PY - 2012/07/02
Y2 - 2019/12/06
TI - Monomial Dynamical Systems in # P-complete
JF - Mathematical Journal of Interdisciplinary Sciences
JA - Math. J. Interdiscip. Sci.
VL - 1
IS - 1
SE - Articles
DO -
UR - https://mjis.chitkara.edu.in/index.php/mjis/article/view/163
AB - In this paper, we study boolean monomial dynamical systems. Colón-Reyes, Jarrah, Laubenbacher, and Sturmfels(2006) studied fixed point structure of boolean monomial dynamical systems of f by associating the dynamical systems of f with its dependency graph χf and Jarrah, Laubenbacher, and Veliz-Cuba(2010) extended it and presented lower and upper bound for the number of cycles of a given length for general boolean monomial dynamics. But, it is even difficult to determine the exact number of fixed points of boolean monomial dynamics. We show that the problem of counting fixed points of a boolean monomial dynamical systems is #P-complete, for which no efficient algorithm is known. This is proved by a 1-1 correspondence between fixed points of f sand antichains of the poset of strongly connected components of χf..
ER -