Perhaps more clearly showing the connection between 'complexity' in the general sense and EMH is this paper[0], showing that even (eps, eps)-weak (or approximate) Nash equilibria are communication-hard (exponential in the number of players), would be the first that has convinced me that markets are highly unlikely to be efficient.
---
Unless I missed it, they don't assert that markets are optimal, which seems to be what you're saying, but merely efficient and thus, it would be hard (but possible) to do better.
> Financially, the “economic calculation problem” of von Mises (1920) and Hayek (1935) suggests, among other things, that, even if a free market is not perfectly efficient, it will certainly be more efficient than a regulatory or government alternative. In other words, even if mispricings occasionally occur, most of the time they are smaller than any other alternative system
So the paper possibly disproves a particular kind of efficiency (weak form efficiency), but that's not the colloquial meaning to which I was referring.
That really blew my mind, because up until that point I guess I had sort of taken it on faith -- without really getting it -- that these game models were accurately representing reality. I guess it sounds obvious after the fact that they aren't, but it was one of the biggest insights I've ever experienced.
It's also a computationally insane assertion, if it were true then markets are capable of computing NP in P (which even with the human element would still be an impressive find; especially considering the `n` it's commonly proposed over in "formal" economic settings is in the area of tens of thousands). It's like people who claim they made a perpetual energy machine are claiming things that are physically insane. Except it's not just some cranks, it's entire fields that haven't caught up to the ideas computer science has discovered.
The adaptive market hypothesis appears to resolve this by tying the efficient market hypothesis to the biology of the computational unit. Since biological systems (appear to) obey the principles of computation, the issue is fixed. Overall it seems a better way forward by connecting pseduo-sciencey intuitive aspects of economics (that violate what we now know about the properties of information) to real science.