Exactly! The definition of an efficient market makes no claim to the market's computational power whatsoever. Computation and efficiency are unrelated. All it means is that the market would make the best use of whatever computations it can carry out. The paper's author, however, quite funnily understands efficiency to imply magical computation, and then "proves" that this would require solving NP-hard problems.
He first understands efficient to mean godlike, and then shows that for God to work, He would need to solve NP-hard problems quickly. Well, duh.
Effiecient market, as I understand it, means that the market would make the best possible desicions given the information it has available. Working with this definition, the market would need to solve NP-complete problems quickly. As I think is obvious, the market cannot (heck, at the speeds the market runs, I doubt it can even solve most P problems in time).
It seems like the definition of effiecent market you are using would mean the market makes the best decisions given the information and computational resources it has.
I would make an even weaker claim, saying the market makes the best possible decision, given the information, computational resources, and known algorithms to utilize the information and computational resources, and given players whose goal is not achieving an optimal outcome from the market.
He first understands efficient to mean godlike, and then shows that for God to work, He would need to solve NP-hard problems quickly. Well, duh.