Re: Isn't this related to chaos theory ?
Not really. I believe that's it's related to the "no free lunch" theorem, or at least something like it can apply. Your standard fractal generator (eg, Fractint) has various optimisations for calculating the "limit cycle" and deciding whether a point leads to "capture" by the attractor, or how long it will take. All nice for making pretty pictures, but if you want to, say, model the weather, you need to iterate to find the final state of the model. The "sensitive dependence on initial condition" part of "chaos theory" does indeed rule out there being a quick solution without having to calculate all the intermediate steps. Same with blockchains or the Byzantine Generals problem: the person provides a proof of work that they have actually done the calculations.