Complexity of ten decision problems in continuous time dynamical systems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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

Original languageEnglish (US)
Title of host publication2013 American Control Conference, ACC 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages6376-6381
Number of pages6
ISBN (Print)9781479901777
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 1st American Control Conference, ACC 2013 - Washington, DC, United States
Duration: Jun 17 2013Jun 19 2013

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619

Other

Other2013 1st American Control Conference, ACC 2013
CountryUnited States
CityWashington, DC
Period6/17/136/19/13

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Complexity of ten decision problems in continuous time dynamical systems'. Together they form a unique fingerprint.

Cite this