---
author:
- Tuhin Sahai
title: 'Dynamical Systems Theory and Algorithms for NP-hard Problems'
---

Computational Complexity, Dynamical Systems Theory, NP-hardness, Heuristic Algorithms, Combinatorial Optimization.

Introduction {#sec:intro}
============

Dynamical systems theory and computational complexity have, predominantly, been developed as independent areas of research over the last century with little interaction and mutual influence. Dynamical systems theory has its origins in the seminal work of Henri Poincaré [@Cit:Poincare] on celestial mechanics. Computational complexity theory, on the other hand, originated in the works of Alan Turing [@Cit:Turing] and Alonzo Church [@Cit:Church] in the 1930s and has played an intimate role in the computing revolution of the twentieth century.

Eventually, dynamical systems theory (or nonlinear dynamics) found broad application beyond celestial mechanics. In particular, it has been used extensively to model and analyze engineering systems [@Cit:Stro], physics of natural phenomena, biological [@Cit:Bio] and chemical processes [@Cit:chem], fluid dynamics [@Cit:turb], and epidemiology [@Cit:epi] to name a few. Moreover, the analysis of dynamical systems is typically intimately tied to numerical methods [@Cit:set_oriented; @Cit:Igor] and scientific computation [@Cit:scientific_comp].

Links to the applications (outlined in the previous paragraph) have played a critical role in the theoretical development of the field. For example, they have influenced the development 