# 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.