Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems

We study worst-case finite-time energy dissipation in quadratic systems with proved global asymptotic stability (GAS). Estimating the maximum retained energy fraction to any fixed positive additive error below 1/2 is NP-hard, even when the input includes a strict quartic Lyapunov function and proof of strictness, both constructed in polynomial time. NP denotes nondeterministic polynomial time. For a partially damped family, the unit-sphere minimum norm of the coupling map equals the structured coefficient distance to loss of GAS. Positive distances at most 1/2 give two-sided inverse-square halving-time bounds with explicit coefficient factors. Polynomial-factor approximation of the least dissipated fraction, halving time or coefficient distance is NP-hard. Additive hardness persists throughout an explicit coefficient neighborhood and under direct damping with exponential stability, a strict quadratic Lyapunov function and a Hurwitz Jacobian. Unless P= NP, where P denotes deterministic polynomial time, no polynomial-time algorithm attains these guarantees on all inputs.