Stabilization problem is a fundamental problem in control theory. There are many literature to achieve stabilization but fewer results are related in computational complexity. Consequently, we consider the computational complexity of stabilization problem.
Given a linear Boolean control network (BCN) $$x(t+1)=Ax(t)+Bu(t),$$ where $x(t)\in\mathbb{F}_2^{n\times 1},u(t)\in\mathbb{F}_2^{m\times 1}$ ($m\leq n$) represent the network state and input (or control) state at time $t$, respectively; $A\in\mathbb{F}_2^{n\times n},B\in\mathbb{F}_2^{n\times m}.$ Denote $\mathbb{F}_2$ as binary field.
The stabilization problem in the linear BCN is to determine whether there is state feedback $u(t)=Kx(t)$ ($K\in\mathbb{F}_2^{m\times n}$) so that all network states of the linear BCN converge to the origin $[0,\cdots,0]$ [1]. Briefly, Stabilization Problem ($\mathbf{SP}$) can be represented as
- Input: two Boolean matrices $A\in\mathbb{F}_2^{n\times n}$ and $B\in\mathbb{F}_2^{n\times m}$ $(m\leq n).$
- Problem: determine whether there is state feedback $u(t)=Kx(t)$ ($K\in\mathbb{F}_2^{m\times n}$) so that all network states of the system $x(t+1)=(A+BK)x(t)$ converge to $[0,\cdots,0].$
Exactly, I have proved a simple case where $K\in\mathbb{F}_2^{n\times 1}$ and all nonzero entries of $K$ do not exceed a given constant $w$ by Finite-Field subset sum problem [2]. $\mathbf{SP}$ is my question and the following is my efforts to solve this problem.
According to [3], for a given Boolean matrix $Q\in\mathbb{F}_2^{n\times n}$ if there exist an invertible Boolean matrix $P_0\in\mathbb{F}_2^{n\times n}$ and a lower triangular matrix $A_0$ whose diagonal elements of $A_0$ are all $0$ such that $$P_0QP_0^{-1}=A_0,$$ then all states of the system $x(t+1)=Qx(t)$ will converge to $[0,\cdots,0].$
Inspired by this conclusion, $\mathbf{SP}$ can convert into whether there exists an invertible Boolean matrix $P_0\in\mathbb{F}_2^{n\times n}$ and a lower triangular matrix $A_0\in\mathbb{F}_2^{n\times n}$ whose diagonal elements are all $0$ such that $P_0(A+BK)P_0^{-1}=A_0.$ By simple calculation, we have \begin{equation} \label{eq:lineareq} BK=A+P_0^{-1}A_0P_0. \end{equation} According to the linear algebra, $\mathbf{SP}$ has a solution $K$ iff $$rank(B)=rank(B,A+P_0^{-1}A_0P_0).$$ Hence, $\mathbf{SP}$ converts into whether there exists an invertible matrix $P_0$ and a lower triangular matrix $A_0$ such that $rank(B)=rank(B,A+P_0^{-1}A_0P_0).$ Finally, Rank Equality Problem ($\mathbf{REP}$) can be denoted as
- Input: given two Boolean matrices $A\in\mathbb{F}_2^{n\times n},B\in\mathbb{F}_2^{n\times m}$ ($m\leq n$)
- Problem: find an invertible matrix $P_0\in\mathbb{F}_2^{n\times n}$ and a lower triangular matrix $A_0$ whose diagonal elements are all $0$ such that $$rank(B)=rank(B,A+P_0^{-1}A_0P_0).$$
Is there a polynomial time algorithm to solve the Rank Equality Problem?
Next, I will give some supporting materials that $\mathbf{SP}$ is NP-complete. By [3], $\mathbf{SP}$ have a solution $K$ iff $\det(\lambda I_n-A-BK)~ mod ~2 =\lambda^n.$ Assume that $K=[k_{ij}]_{m\times n}$ and $$\det(\lambda I_n-A-BK)=\lambda^n+f_1(k_{11},k_{12},\cdots,k_{mn})\lambda^{n-1}+\cdots+f_{n-1}(k_{11},k_{12},\cdots,k_{mn})\lambda+f_n(k_{11},k_{12},\cdots,k_{mn}),$$ hence we have $$f_i(k_{11},k_{12},\cdots,k_{mn}) ~mod~ 2=0,~i=1,\cdots,n.$$ In the following, I will propose a method to convert $f_i(k_{11},k_{12},\cdots,k_{mn}) ~mod~ 2=0,~i=1,\cdots,n $ into Boolean quadratic equations ($\mathbf{QUADEQ}$). For example, let $k_{1,1}k_{1,2}k_{1,3}\cdots k_{1,10}$ be a term of $f_1(k_{11},k_{12},\cdots,k_{mn}),$ then I convert the term into Boolean $\mathbf{QUADEQ}$ ($\mathbf{QUADEQ}$ is NP-complete [4]).
Let $k_{11}k_{12}=y_1,\cdots,k_{1,9}k_{1,10}=y_5,y_1y_2=z_1,y_3y_4=z_2,z_1z_2=q_1,$ therefore $k_{1,1}k_{1,2}k_{1,3}\cdots k_{1,10}$ is equal to $q_1y_5$ with $k_{11}k_{12}=y_1,\cdots,k_{1,9}k_{1,10}=y_5,y_1y_2=z_1,y_3y_4=z_2,z_1z_2=q_1.$ By this way, $f_i(k_{11},k_{12},\cdots,k_{mn}) ~mod~ 2=0,~i=1,\cdots,n$ can convert into Boolean $\mathbf{QUADEQ}$ in polynomial time. Therefore, I conjecture that $\mathbf{SP}$ is NP-complete.
Reference
[1] Cheng, D., Qi, H., & Li, Z. (2010). Analysis and control of Boolean networks: a semi-tensor product approach. Springer Science & Business Media.
[2] Vardy, A. (1997). The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43(6), 1757-1766.
[3] Hernández Toledo, R. A. (2005). Linear finite dynamical systems. Communications in Algebra, 33(9), 2977-2989.
[4] Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.