HEXAGONbeta

Deciding D-stability is coNP-hard

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexitymath.DS — Dynamical Systems

Contributed by Michael Mislan ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

The computational difficulty of D-stability, raised by Chen, Fan and Yu (1995, doi:10.1016/0167-6911(94)00036-U), is addressed by an explicit integer-matrix reduction from PARTITION. For positive weights of total 2T, the construction produces a matrix of order m + 4 that is D-stable exactly when no subset has weight T. When an equal split exists, some positive diagonal scaling has an eigenvalue with strictly positive real part. A Pell recursion supplies the parameters, with a logarithmic search bound and an explicit bound on every matrix entry. These bounds give polynomial binary output length. Together with the classical NP-completeness of PARTITION, the reduction yields coNP-hardness of D-stability and D-semistability, and NP-hardness of strict D-instability, even for a four-dimensional core with attachments at one coordinate. The hardness is in the weak sense for binary encoding. Running-time analysis and the trivial-instance cases are treated conventionally; registered Lean statements verify the explicit arithmetic encoding, bounds and promise dichotomy.

Provenance statement

The text is primarily AI-generated. AI systems assisted the mathematical development, computations and Lean formalization under human direction; human understanding covers some parts of the work.

Formalizations

References

  1. Arrow, Kenneth J.; McManus, Maurice. A Note on Dynamic Stability. Econometrica, vol. 26, no. 3, pp. 448–454. 1958DOI
  2. Balbach, Frank J. The Cook–Levin theorem. Archive of Formal Proofs. 2023. Formal proof developmentlink
  3. Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise. Algorithms in Real Algebraic Geometry. Springer, vol. 10. 2006DOI
  4. Blondel, Vincent; Tsitsiklis, John N. NP-hardness of some linear control design problems. SIAM Journal on Control and Optimization, vol. 35, no. 6, pp. 2118–2127. 1997DOI
  5. Blondel, Vincent D.; Tsitsiklis, John N. A survey of computational complexity results in systems and control. Automatica, vol. 36, no. 9, pp. 1249–1274. 2000DOI
  6. Braatz, Richard P.; Young, Peter M.; Doyle, John C.; Morari, Manfred. Computational complexity of μ\mu calculation. IEEE Transactions on Automatic Control, vol. 39, no. 5, pp. 1000–1002. 1994DOI
  7. Cain, Bryan E. Real, 3×33\times 3, D-stable matrices. Journal of Research of the National Bureau of Standards, Section B: Mathematical Sciences, vol. 80B, no. 1, pp. 75–77. 1976DOI
  8. Canny, John. Some algebraic and geometric computations in PSPACE. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC '88), pp. 460–469. 1988DOI
  9. Casasanta, John-Paolo; Simpson-Porco, John W. A Lyapunov characterization of robust DD-stability with application to decentralized integral control of LTI systems. IEEE Control Systems Letters, vol. 10, pp. 1375–1380. 2026DOI
  10. Chen, Jie; Fan, Michael K. H.; Yu, Cheng-Ching. On DD-stability and structured singular values. Systems & Control Letters, vol. 24, no. 1, pp. 19–24. 1995DOI
Show all 37 referencesShow fewer references
  1. Coxson, Gregory E. The PP-matrix problem is co-NP-complete. Mathematical Programming, vol. 64, no. 1–3, pp. 173–178. 1994DOI
  2. Cross, G. W. Three types of matrix stability. Linear Algebra and its Applications, vol. 20, no. 3, pp. 253–263. 1978DOI
  3. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 Theorem Prover and Programming Language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021DOI
  4. Enthoven, Alain C.; Arrow, Kenneth J. A Theorem on Expectations and the Stability of Equilibrium. Econometrica, vol. 24, no. 3, pp. 288–293. 1956DOI
  5. Forster, Yannick; Kunze, Fabian; Wuttke, Maximilian. Verified Programming of Turing Machines in Coq. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pp. 114–128. 2020DOI
  6. Gäher, Lennard; Kunze, Fabian. Mechanising Complexity Theory: The Cook–Levin Theorem in Coq. 12th International Conference on Interactive Theorem Proving (ITP 2021), vol. 193, pp. 20:1–20:18. 2021DOI
  7. Gantmacher, F. R. The Theory of Matrices. Chelsea Publishing Co., vol. 2. 1959. Translated by K. A. Hirsch
  8. Garey, Michael R.; Johnson, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. 1979
  9. Giorgi, Giorgio; Zuccotti, Cesare. An Overview on DD-stable Matrices. no. 97 (02-15). 2015link
  10. Gurvits, Leonid; Olshevsky, Alexander. On the NP-hardness of checking matrix polytope stability and continuous-time switching stability. IEEE Transactions on Automatic Control, vol. 54, no. 2, pp. 337–341. 2009DOI
  11. Hershkowitz, Daniel. Recent directions in matrix stability. Linear Algebra and its Applications, vol. 171, pp. 161–186. 1992DOI
  12. Horáček, Jaroslav; Hladík, Milan; Černý, Michal. Interval Linear Algebra and Computational Complexity. Applied and Computational Matrix Analysis (MAT-TRIAD 2015), vol. 192, pp. 37–66. 2017arXivDOI
  13. Horn, Roger A.; Johnson, Charles R. Topics in Matrix Analysis. Cambridge University Press. 1991DOI
  14. Impram, Serkan T.; Johnson, Russell; Pavani, Raffaella. The D-stability problem for 4×44\times 4 real matrices. Archivum Mathematicum (Brno), vol. 41, no. 4, pp. 439–450. 2005. MR 2195496, Zbl 1122.15003
  15. Johnson, Charles R. Sufficient conditions for D-stability. Journal of Economic Theory, vol. 9, no. 1, pp. 53–62. 1974DOI
  16. Kanovei, G. V.; Logofet, D. O. D-stability of 4-by-4 matrices. Computational Mathematics and Mathematical Physics, vol. 38, no. 9, pp. 1369–1374. 1998. Translated from Zh. Vychisl. Mat. Mat. Fiz. 38(9) (1998) 1429–1435
  17. Karp, Richard M. Reducibility among combinatorial problems. Complexity of Computer Computations, pp. 85–103. 1972DOI
  18. Kushel, Olga Y. Unifying Matrix Stability Concepts with a View to Applications. SIAM Review, vol. 61, no. 4, pp. 643–729. 2019arXivDOI
  19. Kushel, Olga Y. Recursive determinantal framework for testing D-stability. I. 2026arXivDOI
  20. Lee, Jietae; Edgar, Thomas F. Real structured singular value conditions for the strong DD-stability. Systems & Control Letters, vol. 44, no. 4, pp. 273–277. 2001DOI
  21. Logofet, Dmitrii O. Matrices and Graphs: Stability Problems in Mathematical Ecology. CRC Press. 1993
  22. Nemirovskii, Arkadi. Several NP-hard problems arising in robust stability analysis. Mathematics of Control, Signals, and Systems, vol. 6, no. 2, pp. 99–105. 1993DOI
  23. Poljak, Svatopluk; Rohn, Jiří. Checking robust nonsingularity is NP-hard. Mathematics of Control, Signals, and Systems, vol. 6, no. 1, pp. 1–9. 1993DOI
  24. Renegar, James. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. Journal of Symbolic Computation, vol. 13, no. 3, pp. 255–299. 1992DOI
  25. Renegar, James. On the computational complexity and geometry of the first-order theory of the reals. Part II: The general decision problem. Preliminaries for quantifier elimination. Journal of Symbolic Computation, vol. 13, no. 3, pp. 301–327. 1992DOI
  26. Renegar, James. On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination. Journal of Symbolic Computation, vol. 13, no. 3, pp. 329–352. 1992DOI
  27. The mathlib Community. The Lean Mathematical Library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pp. 367–381. 2020DOI

Version history

  1. v1Submitted by Michael MislanInitial depositCurrentOct 18, 2026