Controllability is Harder to Decide than Accessibility
- 1 September 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Control and Optimization
- Vol. 26 (5) , 1106-1118
Abstract
This article compares the difficulties of deciding controllability and accessibility. These are standard properties of control systems, but complete algebraic characterizations of controllability have proved elusive. The article shows in particular that, for subsystems of bilinear systems, accessibility can be decided in polynomial time, but controllability is NP-hard.Keywords
This publication has 8 references indexed in Scilit:
- A General Theorem on Local ControllabilitySIAM Journal on Control and Optimization, 1987
- Intractable Problems in Control TheorySIAM Journal on Control and Optimization, 1986
- Real addition and the polynomial hierarchyInformation Processing Letters, 1985
- Nonlinear Control Systems: An Introduction1985
- Determination of the Transitivity of Bilinear SystemsSIAM Journal on Control and Optimization, 1979
- Nonlinear controllability and observabilityIEEE Transactions on Automatic Control, 1977
- On some questions of rationality and decidabilityJournal of Computer and System Sciences, 1975
- Quantifier elimination for real closed fields by cylindrical algebraic decompostion1975