# Computational complexity in Boolean network

An Boolean control networks can be expressed as $$$$\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.$$$$ 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$$?

In order to solve this problem, I convert the problem into logical form as following:

$$\begin{equation*} \begin{split} &\forall x_1(0)\cdots\forall x_n(0)\forall x_1(M)\cdots\forall x_n(M)\exists u_1(0)\cdots\exists u_m(0)\exists x_1(1)\cdots\exists x_n(1)\cdots \exists x_1(M-1)\cdots\exists x_n(M-1)\ &\exists u_1(M-1)\cdots\exists u_n(M-1)~~\bigwedge_{i=1}^{n}(f_i(x(0),u(0))\leftrightarrow x_i(1))\wedge \bigwedge_{i=1}^{n}(f_i(x(1),u(1))\leftrightarrow x_i(2))\wedge \cdots\wedge \ &\bigwedge_{i=1}^{n}(f_i(x(M-1),u(M-1))\leftrightarrow x_i(M)).\ \end{split} \end{equation*}$$

According to such expression, I can prove the upper bound of the problem. But I have no idea about how to prove it is $$\Pi_2^p$$-hard.