The Space-Bounded Church–Turing thesis for computing asymptotic stochastic behavior
Statement
Let be a closed, discrete-time stochastic system over a state space , and let its memory be
where the inner supremum ranges over all distributions on and denotes Shannon mutual information. Space-Bounded Church–Turing thesis. The problem of computing the asymptotic behavior of with memory to within precision is in the complexity class
This is presented as a concrete form of the Space-Bounded Church–Turing thesis, also called the Simulation Assertion in the cited source. The statement concerns the space complexity of computing long-term behavior from the system's information-preservation capacity; its resolution is not specified in the supplied text.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.