Polynomial system controllability cannot be fully decided or listed
Controllability of polynomial systems is undecidable and not recursively enumerable
Computational Complexity
Summary
Determining whether certain mathematical systems called polynomial systems can be controlled is a complex problem that the authors study. They prove it is impossible to create a step-by-step method that always decides if these systems are controllable. Moreover, they show that you cannot even list all controllable systems with a systematic procedure. This settles a long-standing question about these systems' behavior.
What this means in practice
- •For control systems engineers: Avoid attempts to develop complete algorithms that decide global controllability for polynomial systems when designing control software.
- •For automated verification tool developers: Recognize that listing all globally controllable polynomial systems is impossible, impacting tool completeness for nonlinear system verification.
A theory result. No direct application yet.
Authors
Jun Liu, Ivan O. Shevchenko
Abstract
Sontag conjectured in 1988 that global controllability of polynomial control systems with rational coefficients is undecidable, but that the controllable systems form a recursively enumerable set. We prove the first part of the conjecture and disprove the second. For every homogeneous polynomial vector field $F$ of odd degree with rational coefficients, we construct an explicit polynomial control system $Σ_F$, with one more state than $F$, that is globally controllable if and only if the origin is \emph{not} globally asymptotically stable for $\dot x=F(x)$. By a recent result, the homogeneous polynomial vector fields with a globally asymptotically stable origin form a set that is recursively enumerable but not decidable. Consequently, global controllability of polynomial systems is undecidable, and the controllable polynomial systems are not recursively enumerable. The same conclusions hold for systems of the form $\dotξ=f(ξ)+Bu$ with a polynomial drift and a constant input matrix.