Overview of complexity and decidability results for three classes of elementary nonlinear systems

It has become increasingly apparent this last decade that many problems in systems and control are NP-hard and, in some cases, undecidable. The inhere nt complexity of some of the most elementary problems in systems and contro l points to the necessity of using alternative approximate techniques to de al with problems that are unsolvable or intractable when exact solutions ar e sought. We survey some of the decidability and complexity results available for thr ee classes of discrete time nonlinear systems. In each case, we draw the li ne between the problems that are unsolvable, those that are NP-hard, and th ose for which polynomial time algorithms are known.