  


Complexity of Ten Decision Problems in Continuous Time Dynamical Systems
Amir Ali Ahmadi(a_a_amit.edu) Abstract: 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 pseudopolynomial 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 NPhardness proof of testing local asymptotic stability for polynomial vector fields to the case of trigonometric differential equations of degree four. Keywords: Stability f nonlinear systems, Exactness of semidefinite programming based methods Category 1: Applications  Science and Engineering (Control Applications ) Category 2: Nonlinear Optimization (Systems governed by Differential Equations Optimization ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Submitted for publication. Download: [PDF] Entry Submitted: 10/28/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  