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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90918 https://orcid.org/0000-0002-9383-6071 https://orcid.org/0000-0002-8712-7092 |
| _version_ | 1811083436685787136 |
|---|---|
| author | Ahmadi, Amir Ali Majumdar, Anirudha Tedrake, Russell Louis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ahmadi, Amir Ali Majumdar, Anirudha Tedrake, Russell Louis |
| author_sort | Ahmadi, Amir Ali |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:32:44Z |
| format | Article |
| id | mit-1721.1/90918 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:32:44Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/909182022-09-28T08:28:08Z Complexity of ten decision problems in continuous time dynamical systems Ahmadi, Amir Ali Majumdar, Anirudha Tedrake, Russell Louis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Majumdar, Anirudha Tedrake, Russell Louis 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. 2014-10-14T19:30:56Z 2014-10-14T19:30:56Z 2013-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-0178-4 978-1-4799-0177-7 978-1-4799-0175-3 0743-1619 http://hdl.handle.net/1721.1/90918 Ahmadi, Amir Ali, Anirudha Majumdar, and Russ Tedrake. “Complexity of Ten Decision Problems in Continuous Time Dynamical Systems.” 2013 American Control Conference (June 2013). https://orcid.org/0000-0002-9383-6071 https://orcid.org/0000-0002-8712-7092 en_US http://dx.doi.org/10.1109/ACC.2013.6580838 Proceedings of the 2013 American Control Conference Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Ahmadi, Amir Ali Majumdar, Anirudha Tedrake, Russell Louis Complexity of ten decision problems in continuous time dynamical systems |
| title | Complexity of ten decision problems in continuous time dynamical systems |
| title_full | Complexity of ten decision problems in continuous time dynamical systems |
| title_fullStr | Complexity of ten decision problems in continuous time dynamical systems |
| title_full_unstemmed | Complexity of ten decision problems in continuous time dynamical systems |
| title_short | Complexity of ten decision problems in continuous time dynamical systems |
| title_sort | complexity of ten decision problems in continuous time dynamical systems |
| url | http://hdl.handle.net/1721.1/90918 https://orcid.org/0000-0002-9383-6071 https://orcid.org/0000-0002-8712-7092 |
| work_keys_str_mv | AT ahmadiamirali complexityoftendecisionproblemsincontinuoustimedynamicalsystems AT majumdaranirudha complexityoftendecisionproblemsincontinuoustimedynamicalsystems AT tedrakerusselllouis complexityoftendecisionproblemsincontinuoustimedynamicalsystems |