The whole trick behind that paper is to take the definition of "market efficiency" to mean that all profit opportunities, even those requiring solving difficult computational problems, are identified immediately. Then, you encode NP-complete problems as exchange offerings, and the efficient trader would have to be an oracle for it.
This is, obviously, not what most people have in mind by market efficiency, and simply means that the definition needs to be generalized to account for lags in pure inferential operations -- i.e. "all profit opportunities are exploited as soon as a real-world computation system could notice it". Still a strong claim, but not trivially refuted by turning exchanges into oracles by clever choice of exchange offers.
Note: no one thinks all markets are efficient in the "EMH sense", only highly-liquid ones like electronic securities exchanges in developed countries. Also, it's different from the sense of Pareto-efficient that most political advocates of markets mean when advocating them.
"And even if it were real, it would only be efficient if P=NP."
Because finding global optima is hard? I grant that, but:
1) things can be intractably hard even if P=NP - O(n^10000) is in P, and there are complexity classes strictly harder than P (e.g. EXPTIME)), and since there are innumerable moves anyone could take out into the future "optimal resource distribution" could plausibly fall in EXPTIME.
2) Regardless, any single entity determining optimal resource distribution also needs to solve the same problem.
If you were saying something else, please clarify.
The difference is that you can have a model that is not precise and which still makes useful predictions. You can't have a proof that's not precise and still proves P=NP.
Note that it is not "the existence of free markets" that is assumed and breaks things, but the existence of free markets with a particular formulation of a particular property. As strictly defined there, weak-form efficiency also allows seems to allow FTL communication.
Unfortunately, in a market where the number of choices available are limited by physical space (Do you know what it looks like when 15 different ISPs all run their own last-mile hardware? Would you like to live in a city where 8 different sewage disposal companies all run their own waste pipelines?), a sufficiently free market is practically impossible.
In some cases, even a nebulously defined "sufficiently" free market is impossible.
There is no such thing as a free market: it is an idealistic theoretical construct.
And even if it were real, it would only be efficient if P=NP[0].
0. http://arxiv.org/abs/1002.2284