Complexity of Maximum Fixed Point Problem in Boolean Networks

摘要

A Boolean network (BN) with n components is a discrete dynamical system described by the successive iterations of a function f : {0, 1}~n → {0, 1}~n. This model finds applications in biology, where fixed points play a central role. For example in genetic regulation they correspond to cell phenotypes. In this context, experiments reveal the existence of positive or negative influences among components: component i has a positive (resp. negative) influence on component j, meaning that j tends to mimic (resp. negate) i. The digraph of influences is called signed interaction digraph (SID), and one SID may correspond to multiple BNs. The present work opens a new perspective on the well-established study of fixed points in BNs. Biologists discover the SID of a BN they do not know, and may ask: given that SID, can it correspond to a BN having at least k fixed points? Depending on the input, this problem is in P or complete for NP, NP~(#P) or NEXPTIME.