patternMinor
Reference Request: Overlaps between complexity theory and dynamical systems?
Viewed 0 times
referencetheorydynamicaloverlapsrequestsystemsbetweenandcomplexity
Problem
Per Wikipedia:
In mathematics, a dynamical system is a system in which a function
describes the time dependence of a point in a geometrical space.
Examples include the mathematical models that describe the swinging of
a clock pendulum, the flow of water in a pipe, and the number of fish
each springtime in a lake.
At any given time a dynamical system has a state given by a set of
real numbers (a vector) that can be represented by a point in an
appropriate state space (a geometrical manifold). The evolution rule
of the dynamical system is a function that describes what future
states follow from the current state. Often the function is
deterministic; in other words, for a given time interval only one
future state follows from the current state however, some
systems are stochastic, in that random events also affect the
evolution of the state variables.
Is there any result on dynamical system (i.e. solving dynamical equations, finding asymptotic states to a system, dynamics in chaotic system) with complexity theory, hardness for finding a solution, etc.?
Thanks
In mathematics, a dynamical system is a system in which a function
describes the time dependence of a point in a geometrical space.
Examples include the mathematical models that describe the swinging of
a clock pendulum, the flow of water in a pipe, and the number of fish
each springtime in a lake.
At any given time a dynamical system has a state given by a set of
real numbers (a vector) that can be represented by a point in an
appropriate state space (a geometrical manifold). The evolution rule
of the dynamical system is a function that describes what future
states follow from the current state. Often the function is
deterministic; in other words, for a given time interval only one
future state follows from the current state however, some
systems are stochastic, in that random events also affect the
evolution of the state variables.
Is there any result on dynamical system (i.e. solving dynamical equations, finding asymptotic states to a system, dynamics in chaotic system) with complexity theory, hardness for finding a solution, etc.?
Thanks
Solution
This is a well-researched area. For a representative result, see Kawamura's proof that solving ODEs is difficult.
A different line of works studies the hardness of computing Nash equilibria and related problems. See for example the recent breakthrough of Bitansky, Paneth and Rosen, who base hardness of cryptographic assumptions; earlier work based it on complexity theoretic assumptions.
A different line of works studies the hardness of computing Nash equilibria and related problems. See for example the recent breakthrough of Bitansky, Paneth and Rosen, who base hardness of cryptographic assumptions; earlier work based it on complexity theoretic assumptions.
Context
StackExchange Computer Science Q#53757, answer score: 3
Revisions (0)
No revisions yet.