Of course this doesn't mean markets aren't within some small constant factor of being perfectly efficient.
Also worth noting is that the expensive nature of being perfectly informed is one of the main drivers of the large sizes of firms. We can measure how well markets are doing with respect to the amount of excess, beyond normal profit that producers can capture in the long term. Current polarization of wealth and excess of rent suggest no, we are very far from efficient markets.
There is an argument one can give that the abstraction of interacting humans leads to a computer more powerful than a regular turing machine. I don't believe this but everyone who thinks AI is not possible on a turing machine does.
Subset-sum can be approximated within 1+epsilon for any requested epsilon>0 [a PTAS]
MAX-3SAT can be approximated within 8/7 and not better. Vertex cover can be aproximated within 2 and its not known if that's optimal.
Set cover can be approximated within O(log n) and not better.
Clique and TSP have no sensible approximation.
I would argue that potentially a loss of factor 2 is not an order of magnitude away from optimal. I don't know what is the situation for markets.