From linear to nonlinear: some complexity comparisons
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (01912216) , 2916-2920
- https://doi.org/10.1109/cdc.1995.478585
Abstract
This paper deals with the computational complexity, and in some cases undecidability, of several problems in nonlinear control. The objective is to compare the theoretical difficulty of solving such problems to the corresponding problems for linear systems. In particular, the problem of null-controllability for systems with saturations (of a "neural network" type) is mentioned, as well as problems regarding piecewise linear (hybrid) systems. A comparison of accessibility, which can be checked fairly simply by Lie-algebraic methods, and controllability, which is at least NP-hard for bilinear systems, is carried out. Finally, some remarks are given on analog computation in this context.Keywords
This publication has 13 references indexed in Scilit:
- Some complexity questions regarding controllabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the Computational Power of Neural NetsJournal of Computer and System Sciences, 1995
- Dynamical Systems with Saturation NonlinearitiesPublished by Springer Nature ,1994
- On the computational power of neural netsPublished by Association for Computing Machinery (ACM) ,1992
- Turing computability with neural netsApplied Mathematics Letters, 1991
- Controllability is Harder to Decide than AccessibilitySIAM Journal on Control and Optimization, 1988
- A General Theorem on Local ControllabilitySIAM Journal on Control and Optimization, 1987
- Real addition and the polynomial hierarchyInformation Processing Letters, 1985
- Remarks on piecewise-linear algebraPacific Journal of Mathematics, 1982
- Nonlinear regulation: The piecewise linear approachIEEE Transactions on Automatic Control, 1981