# Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed.

Say, for instance, as input we have a start configuration of the chaotic Rule 30 cellular automata and a time-step $$t$$, and as output, we require the configuration at time-step $$t$$.

What can be said about the computational complexity of such a computation?

Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the CA at step $$t$$, given the initial configuration, you just need to run the rule for $$t$$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such CA is linear in $$t$$.
• This answer is not quite right; the running time is actually quadratic in $t$, as explained in the link in my comment above. The reason is that you need to simulate up to $t$ cells. Thus, simulating a single step takes $O(t)$ time, not $O(1)$ time. Multiply that by $t$ steps, and you get $O(t^2)$ time. As explained in the link I provided, it is an open question whether we can do substantially better. – D.W. Oct 18 '19 at 17:59