Complexity of Ten Decision Problems in Continuous Time Dynamical Systems

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) al...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-10
Main Authors: Amir Ali Ahmadi, Majumdar, Anirudha, Tedrake, Russ
Format: Article
Language:English
Subjects:
Algorithms
Collision avoidance
Collision dynamics
Control theory
Decision theory
Differential equations
Dynamical systems
Economic models
Equilibrium
Fields (mathematics)
Invariance
Liapunov functions
Mathematical analysis
Polynomials
Stability
Trajectories
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422