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$ ?

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.