Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems

• Quadratic energy redistribution with linear damping appears in reduced fluid and plasma models, while Lyapunov bounds may overestimate energy-halving times.Source: §I · p. 1
• MT is the maximum retained Euclidean energy fraction at any T ≥ 0 over unit full-state initial conditions, including arbitrary damped coordinates.Source: §I · p. 1
• The paper asks whether strict Lyapunov certificates permit accurate polynomial-time estimation; MT ≤ 1/2 guarantees halving, and 1 − MT is the least dissipated fraction.Source: §I · p. 1

A. Related work

• Convex bounds address MT using the observable ∥z∥2 and the unit initial sphere.Source: A. Related work · p. 1
• Convergent moment and SOS hierarchies bound minimum perturbation intensity for unsafe reachability.Source: A. Related work · p. 1
• Existing trajectory correspondences alone do not bound full-state Euclidean energy for arbitrary auxiliary initial states.Source: A. Related work · p. 1

B. Contributions

• Retained-energy estimation is NP-hard at every fixed positive additive error below 1/2, even with an input strict quartic Lyapunov function and rational SOS proof.Source: B. Contributions · p. 1
• For partial damping, minimum unit-sphere coupling norm equals structured coefficient distance to loss of GAS and yields inverse-square halving-time bounds for distances in (0, 1/2].Source: B. Contributions · p. 1
• Additive hardness persists in the coefficient ball and under direct damping, including systems with global exponential stability, a strict quadratic Lyapunov function, and a Hurwitz Jacobian.Source: B. Contributions · p. 1

C. Preliminaries and notation

• A strict global Lyapunov polynomial is radially unbounded, positive away from the origin, zero at the origin, and has strictly negative derivative away from it.Source: C. Preliminaries and notation · p. 1
• GAS adds global convergence and forward completeness to local asymptotic stability, which requires Lyapunov stability and local convergence to zero.Source: C. Preliminaries and notation · p. 1
• Rational data, time horizons, and variable indices are binary encoded, and running time counts bit operations.Source: C. Preliminaries and notation · p. 1
• An additive-β estimate has absolute error at most β, while an α-approximation lies between J/α and αJ for J > 0.Source: C. Preliminaries and notation · p. 2
• ∃R captures feasibility of rational polynomial constraints by polynomial-time reduction, and ∀R consists of its complements.Source: C. Preliminaries and notation · p. 2

II. ENERGY EXCHANGE AND LYAPUNOV FUNCTIONS

• Every solution is forward complete with nonincreasing Euclidean norm, and the origin is Lyapunov stable for every q.The energy derivative and Jacobian coupling vanish at the origin as described in the lemma and its proof.Source: §II · p. 2
• The quartic correction −y⊤q(x) supplies strict dissipation away from the origin when q has no nonzero roots.On y = 0, the energy derivative vanishes; the correction’s derivative is −2C, and the quartic coefficient B + 1 ensures global positivity.Source: §II · p. 2
• The degree-four polynomial is positive definite and radially unbounded for every q, and it is strict exactly when q−1(0) = {0}.For rational Q, the polynomial and its negative derivative have explicit rational weighted SOS decompositions.Source: §II · p. 2
• Theorem 3 characterizes GAS by the absence of nonzero roots of q: the largest invariant subset of {Ė = 0} is {(x, 0): q(x) = 0}.LaSalle’s invariance principle gives global attraction when this subset is only the origin; homogeneity makes any nonzero root preclude local attraction.Source: §II · p. 2
• A strict global polynomial Lyapunov function has minimum degree four for GAS systems in this family; no strict quadratic one exists, even locally.The quartic construction attains this degree, whereas the Euclidean energy is non-strict.Source: §II · pp. 2–3
• Figure 2 illustrates a unit-circle residual image with γ(bq) = ε = 1/8 and GAS indicated.The caption identifies the solid marking as ε and attributes the GAS statement to Theorem 5.Source: Figure 2 · p. 3

III. DISTANCE TO LOSS OF GAS AND HALVING TIME

• The structured coefficient distance to a non-GAS system is γ(q), and every coefficient perturbation smaller than γ(q) preserves GAS.The residual changes by at most the Frobenius coefficient distance.Source: §III · p. 3
• If ∥q(x)∥2 ≥ µ∥x∥4 for all x with 0 < µ ≤ 1/4, unit-initial-state solutions satisfy ρ(t) ≤ 32(B + 1)2/(µt).This residual condition supplies a uniform decay bound from every unit initial state.Source: §III · p. 3
• Every system has a unit initial state whose squared norm remains at least 1 − 8γ(q)2t for all t ≥ 0.Minimizing the coupling yields a slow trajectory; zero coupling gives an equilibrium.Source: §III · p. 3
• Theorem 8 bounds T1/2 between 1/(16γ2) and 64(B+1)2/γ∗2, with both endpoints infinite when γ = 0.Here γ∗ = min(γ, 1/2), and finite halving time is equivalent to GAS.Source: §III · p. 3
• For 0 < γ ≤ 1/2, the halving-time upper bound is 1024(B + 1)2 times the lower bound, and γ is the distance to loss of GAS.The bounds are 1/(16γ2) ≤ T1/2 ≤ 64(B+1)2/γ2 when γ ≤ 1/2.Source: §III · pp. 3–4

IV. COMPLEXITY OF EXACT STABILITY

• A formula has exactly one true literal per clause if and only if its encoded quadratic map has a nonzero real common root.Satisfying assignments yield roots (1, b); when h = 0, every a_i = 0, excluding spurious nonzero roots.Source: §IV · p. 4
• GAS and LAS decisions are strongly coNP-hard with integer field coefficients of magnitude at most six; deciding strictness of the polynomial-time-constructed V4 is coNP-hard.The reduction maps unsatisfiability to asymptotic stability, with uniform coefficient bounds.Source: §IV · p. 4
• LAS, GAS, and strictness of the quartic are ∀R-complete for rational symmetric inputs, even with integer field coefficients of magnitude at most six.Their complement properties are ∃R-complete.Source: §IV · p. 4
• Deciding whether every system within coefficient distance R of a rational center is GAS is ∀R-complete, even at radius one around centers with proved GAS.The reduction appends the norm constraint to make the center GAS.Source: §IV · p. 4

Residual lower bound

• The section’s residual lower-bound argument rounds normalized coordinates to Boolean values, forcing every clause and contradicting unsatisfiability below the stated threshold.The derived bound is κ2 ≥ µ0.Source: §V · pp. 4–5

Theorem 14

• Appending ε∥x∥2 removes nonzero equilibria while preserving the residual gap used to separate the two formula cases at a common time.Theorem 14 uses τp as that evaluation time.Source: §V · p. 5
• For every fixed rational 0 < β < 1/2, estimating retained energy at τp is NP-hard despite polynomial-time strict quartic Lyapunov and rational SOS certificates.Satisfiable inputs retain at least 1 − 1/p, while unsatisfiable inputs retain at most 1/p; Fig. 3 schematizes the bounds.Source: §V · p. 5, Figure 3 · p. 5
• The reduction also makes polynomial-factor approximation NP-hard for halving time, coupling norm, and least dissipated fraction, with separation ratios 4d2K2τ, τp, and 4d2τp, respectively.The bounds apply across all constructed inputs.Source: §V · p. 5

Coefficient perturbations

• Every tuple in the ε/2 coefficient ball is GAS, and for each fixed polynomial-time rule mapping source formulas to rational tuples there, additive-β estimation of retained fraction at τp is NP-hard for fixed rational 0 < β < 1/2 − 1/p.On satisfiable inputs, fMτp ≥ 1 − 9/(32d2τp); on unsatisfiable inputs, fMτp ≤ 4/(7K).Source: §V · p. 5

Direct damping

• Direct damping preserves additive hardness while making every system globally exponentially stable with a strict quadratic Lyapunov function and Hurwitz Jacobian.At Tp, the retained fraction is e^-1/p on satisfiable inputs and at most 1/(2K) on unsatisfiable inputs.Source: §V · p. 6

Polynomial systems

• For every fixed polynomial degree bound k ≥ 2, additive retained-energy estimation remains NP-hard, as do polynomial-factor approximation of halving time and positive dissipated fraction.The hardness also holds with strict quartic Lyapunov proofs in the input.Source: §V · p. 6

Conclusion

• Even with strict Lyapunov proofs in the input, estimating MT within any fixed rational additive error 0 < β < 1/2 is NP-hard.The paper states that hierarchy convergence therefore cannot guarantee polynomial worst-case runtime at this accuracy unless P = NP.Source: §VI · p. 6

Future work

• Future work seeks sharper dependence on B in halving-time bounds and conditions on q that permit polynomial-time MT approximation with explicit error bounds.Source: §VI · p. 6

Theorem 2 expansion

• The appendix begins the square expansion for Theorem 2, including a residual norm term involving y − q(x).Source: Appendix A · p. 7

Residual identities

• The proof isolates two residuals, BX2 − C and 4BXY − ∥Dq(x)⊤y∥2, after expressing the other terms as weighted sums of squares.The construction vectorizes Qi and xx⊤ identically and applies Lagrange’s identity to produce residual squares.Source: Appendix A · p. 7

List construction

• Literal lists retain ordered index pairs with half the displayed weights; diagonal squares vanish and reversed pairs recover the unordered sums.Source: Appendix A · p. 7
• Fixed-depth loops construct the lists in polynomial bit time using exact rational arithmetic, and the identities establish non-negativity.For fixed p and fixed r0, intermediate integers are polynomially bounded in the input length; Euclidean fraction reduction preserves the time bound.Source: Appendix A · p. 7

Encoding the source problem

• The reduction starts from variables χi in [1/2, 2] and equations χi = 1, χi + χj = χℓ, or χiχj = 1.Source: Appendix B · p. 7

Quadratic encoding

• Auxiliary variables encode the interval inequality as a square while keeping doubled coefficients within six.The construction sets ωi = ξi and replaces 5hξi with 3hξi + 2hωi.Source: Appendix B · p. 7

Correctness

• At common roots, the constructed equations force χi into [1/2, 2] and recover the source equations after division by h2; conversely, each source solution gives a nonzero real root.Only the real witness uses square roots; the constructed coefficients remain rational.Source: Appendix B · p. 7
• The reduction maps infeasibility exactly to GAS and quartic strictness, with dimension d = 3n+1 and m = 2n+neq.Source: Appendix B · p. 7

Construction bounds

• The constructed tuple has polynomial bit-time size, with each component containing at most five monomials and B ≤ 45n/2 + 3neq.The field coefficients have magnitude at most six.Source: Appendix B · p. 7