Abstract
This paper investigates the intersection of control theory and computational complexity, specifically focusing on the stability of polynomial dynamical systems. The authors demonstrate that determining the stability of cubic polynomial systems is strongly NP-hard. Furthermore, the research explores the limitations of Sum of Squares (SOS) programming, showing that while SOS is a powerful tool for finding stability certificates, polynomial Lyapunov functions do not always exist for stable systems. The paper provides new converse theorems establishing conditions under which SOS methods are guaranteed to succeed, while highlighting the inherent computational challenges in the field.
Introduction
In the study of dynamical systems—ranging from robotics and aerospace to chemical reaction networks—the fundamental question of stability is paramount. A system is stable if, when perturbed from its equilibrium, it eventually returns to it. The standard mathematical approach to proving stability involves finding a Lyapunov function: a scalar "energy" function that strictly decreases along the system's trajectories.
With the advent of convex optimization, Sum of Squares (SOS) programming has emerged as a primary computational method for automatically searching for these Lyapunov functions. However, the theoretical foundations of this approach have long been shadowed by two critical questions:
- Complexity: How computationally difficult is it to decide if a polynomial system is stable?
- Converse Questions: If a system is stable, is there always a polynomial (or SOS) Lyapunov function that proves it, or are we searching for a certificate that may not exist?
Computational Complexity of Stability
A major contribution of this research is the proof that deciding the local or global asymptotic stability of cubic vector fields (polynomial systems of degree 3) is strongly NP-hard. This result suggests that there is no efficient, general-purpose algorithm for stability analysis; the difficulty is intrinsic to the mathematics of the systems themselves.
To establish this, the authors performed a multi-step reduction from a known hard combinatorial problem, ONE-IN-THREE 3SAT. This was reduced to the problem of checking the positivity of a quartic form (a degree-4 polynomial), which was then mapped to the stability of a cubic vector field. This hardness result extends beyond simple stability to related problems such as collision avoidance and the synthesis of stabilizing controllers.
The Limits of Polynomial Certificates
While practitioners often search for polynomial Lyapunov functions, this paper demonstrates that polynomials are not a universal language for stability. The authors constructed an explicit example of a quadratic system in just two variables that is globally stable but possesses no polynomial Lyapunov function of any degree. This counterexample proves that even for very simple systems, the "energy" function required to prove stability may be non-polynomial, placing a hard limit on the reach of standard SOS techniques.
Furthermore, the paper identifies a "degree explosion" phenomenon. For homogeneous systems (where all terms have the same degree), the authors show that even when a polynomial Lyapunov function exists, the required degree can be arbitrarily large. This explains why SOS solvers often require many iterations or high-degree searches to find a solution.
Converse SOS Theorems and the SOS Gap
SOS programming is a relaxation of the stability problem; it is computationally easier to check if a polynomial is a sum of squares than to check if it is globally non-negative. This paper clarifies the relationship between these two concepts using tools from algebraic geometry, specifically the Positivstellensatz.
The authors provide new "converse" results, proving that for planar (two-dimensional) or homogeneous vector fields, the existence of a polynomial Lyapunov function implies the existence of an SOS Lyapunov function, provided the degree is allowed to increase. However, they also warn of a lack of monotonicity: a system might have a Lyapunov certificate at degree 4, fail to have one at degree 6, and then have one again at a higher degree. This non-monotonic behavior suggests that practitioners should not necessarily abandon a search if a higher-degree iteration fails.
Conclusion and Future Work
This work establishes rigorous bounds on the complexity of stability analysis and the efficacy of SOS programming. While cubic systems are now known to be NP-hard, the complexity of quadratic systems remains an open question. Additionally, the broader question of decidability—whether an algorithm can ever exist to determine stability for all polynomial systems—remains one of the great unsolved problems in the field, as conjectured by Vladimir Arnold. Future research will focus on extending converse SOS guarantees to higher-dimensional, non-homogeneous systems and further mapping the frontier of decidability in dynamical systems.
Summary updated