The continuous Skolem-Pisot problem (Q708215)

The authors consider a dynamical system with the updating trajectory \(\frac{dx(t)}{dt}=Ax(t)\), where \(A\in {\mathbb R}^{n\times n}\) and the initial point \(x(0)\in {\mathbb R}^n\) are given with entries being algebraic numbers. They are interested in determining whether this trajectory ever reaches a given hyperplane, thus the problem is equivalent to determining whether there exists \(t\in {\mathbb R}_{\geq 0}\) such that \(c^T\exp(At)x(0)=0\), where \(c\in {\mathbb R}^n\) defines the hyperplane (the entries of \(c\) are algebraic numbers, too.) This is the continuous Skolem-Pisot problem. The authors show that for instances of size two or less this problem is decidable. The decidability in general is left open. Determining if \(c^T\exp(At)x(0)=0\) reaches zero is computationally equivalent to determining whether a given real-valued exponential polynomial \(f(z)=\sum_{j=1}^m P_j(z)\exp(\theta_j z)\), where each \(P_j\) is a polynomial, ever reaches zero for a positive real value. This is also equivalent to determining whether the solution \(y(t)\) of an ordinary differential equation \(y^{(k)}+a_{k-1}y^{(k-1)}+\dots+a_0y=0\) with given initial conditions \(y^{(k-1)}(0),y^{(k-2)}(0),\dots,y(0)\) ever reaches zero. The authors also show that it is NP-hard to decide if a given linear recurrent sequence is nonnegative.