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_iin{0,1},i=1,cdots,n}.$

Given initial
state $x ( 0 ) = x^0in mathcal{X}$ and destination state $x^din 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^din 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)cdotsforall x_n(0)forall x_1(M)cdotsforall x_n(M)exists u_1(0)cdotsexists u_m(0)exists x_1(1)cdotsexists x_n(1)cdots exists x_1(M-1)cdotsexists x_n(M-1)\
&exists u_1(M-1)cdotsexists 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
cdotswedge \
&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.