Controllability of polynomial systems is undecidable and not recursively enumerable
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 ẋ=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 ξ̇=f(ξ)+Bu with a polynomial drift and a constant input matrix.
Related
- A non-recursively enumerable set W⊆N, where N\W is recursively enumerable and the predicate n∈W expresses a fundamental property of n
- Trinomial containment in polynomial ideals is undecidable
- Lyapunov stability of polynomial vector fields is undecidable
- Global asymptotic stability of homogeneous polynomial vector fields is undecidable
- Controllability of time-varying lumped semilinear systems
BibTeX
@misc{liu2026controllability,
title = {{Controllability of polynomial systems is undecidable and not recursively enumerable}},
author = {Jun Liu and Ivan O. Shevchenko},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26832},
eprint = {2610.26832},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26832},
}
RIS
TY - UNPB
TI - Controllability of polynomial systems is undecidable and not recursively enumerable
AU - Jun Liu
AU - Ivan O. Shevchenko
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26832
UR - https://arxiv.org/abs/2610.26832
AB - 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 ẋ=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 ξ̇=f(ξ)+Bu with a polynomial drift and a constant input matrix.
ER -