TY - GEN

T1 - Complexity of ten decision problems in continuous time dynamical systems

AU - Ahmadi, Amir Ali

AU - Majumdar, Anirudha

AU - Tedrake, Russ

PY - 2013

Y1 - 2013

N2 - We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an equilibrium point in the sense of Lyapunov, boundedness of trajectories, convergence of all trajectories in a ball to a given equilibrium point, existence of a quadratic Lyapunov function, invariance of a ball, invariance of a quartic semialgebraic set under linear dynamics, local collision avoidance, and existence of a stabilizing control law. We also extend our earlier NP-hardness proof of testing local asymptotic stability for polynomial vector fields to the case of trigonometric differential equations of degree four.

AB - We show that for continuous time dynamical systems described by polynomial differential equations of modest degree (typically equal to three), the following decision problems which arise in numerous areas of systems and control theory cannot have a polynomial time (or even pseudo-polynomial time) algorithm unless P=NP: local attractivity of an equilibrium point, stability of an equilibrium point in the sense of Lyapunov, boundedness of trajectories, convergence of all trajectories in a ball to a given equilibrium point, existence of a quadratic Lyapunov function, invariance of a ball, invariance of a quartic semialgebraic set under linear dynamics, local collision avoidance, and existence of a stabilizing control law. We also extend our earlier NP-hardness proof of testing local asymptotic stability for polynomial vector fields to the case of trigonometric differential equations of degree four.

UR - http://www.scopus.com/inward/record.url?scp=84883493678&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883493678&partnerID=8YFLogxK

U2 - 10.1109/acc.2013.6580838

DO - 10.1109/acc.2013.6580838

M3 - Conference contribution

AN - SCOPUS:84883493678

SN - 9781479901777

T3 - Proceedings of the American Control Conference

SP - 6376

EP - 6381

BT - 2013 American Control Conference, ACC 2013

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2013 1st American Control Conference, ACC 2013

Y2 - 17 June 2013 through 19 June 2013

ER -