Computational complexity in Boolean network
An Boolean control networks can be expressed as \begin{equation} \label{ControlBN} \left{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ {x_{2}(t+1)=f_{2}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ {\vdots} \ {x_{n}(t+1)=f_{n}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \ \end{array}\right. \end{equation} where $x_i,~i=1,\dots,n,$ are state nodes, $x_i(t)\in{0,1},\,i=1,\cdots,n$ are the value of the state node $x_i$ at time t. $u_i,~i=1,\dots,m$ are control nodes, $u_i(t)\in{0,1},\,i=1,\cdots,m,$ are the value of the state node $u_i$ at time t, and $f_i:{0,1}^{n+m}\rightarrow {0,1},\,i=1,\dots,n$ are Boolean functions.
Consider the above system, Denote its state space as $\mathcal{X}={(x_1,\cdots,x_n)|x_i\in{0,1},i=1,\cdots,n}.$
Given initial state $x ( 0 ) = x^0\in \mathcal{X}$ and destination state $x^d\in \mathcal{X}$. Destination state $x^d$ is said to be reachable from the initial state $x^0$ at time $s>0,$ if there exists a sequence of controls ${u(t)|t=0,1,\cdots,s-1}$, where $u(t)=(u_1(t),\cdots,u_m(t))$, such that the trajectory of the above system with initial value $x^0$ will reach $x^d $ at time $t=s.$
The above system is said to be controllable, for any $x^0,x^d\in \mathcal{X},$ $x^d$ is reachable from $x^0.$
$M$-step Controllability Problem is defined as
Input: Given an Boolean Control Networks with $n$ state variables $x_1,\cdots,x_n,$ $m$ controls $u_1,\cdots,u_m,$ Boolean function $f_1,\cdots,f_n:{0,1}^{n+m}\rightarrow {0,1}.$ Given constant $M.$
Problem: for any destination state $x^d$ and initial state $x^0$, whether or not there exists a sequence of controls ${u(0),\cdots,u(M-1)}$ such that $x^d$ is reachable from $x^0$? 490