Computational Complexity is about asymptotics so constant factors are irrelevant. In this case if perfects markets require numbers of operations that grow astronomically with respect to input and P <> NP then the best we could do are hueristics and approximations. Indeed it is possible (I think likely) that in many cases even getting good approximations will be in NP.
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.
Generally with NP-complete problems - that small constant factor is still often an order of magnitude away from optimal (path finding/search/salesman/shortest subsequence etc).
