Could markets compute equilibria?
Computing an equilibrium is not needed for implementing it. This was the mistake of Lange and co. and was decisively rebutted by Hayek.
If you want a mathematical formulation, simply take a tatonement process. Given prices, each individual needs to compute her net demand correspondence. Under different tatonement mechanisms, which are an idealization of the dynamic process of price adjustment in the real-world economy, prices should converge to approximate equilibria. In both experimental settings and in financial markets, there is ample evidence for convergence.