Markets are efficient (current prices fully reflect all information available in past prices) if and only if every decision problem thats solution can be efficiently verified (NP) by a computer, can also be efficiently solved by a computer (P). In polynomial time.
The Paper. Aas expected, "If EMH then P=NP" is quite intuitive, to prove the converse Philip Maymin shows how markets can be "programmed" to to solve NP-complete problems.
So I ask myself, when the market still played the Black Scholes game and if the valuation of, say, a certain class of options was NP-complete, then that market segment was still efficient?
However, it serves the intuition that markets become increasingly inefficient as the time series lengthen or become more frequent. In an inefficient market there exist exploitable profit opportunity.
The fact that market efficiency and computational efficiency are linked suggests that it was beneficial if fast algorithms for the valuation of instruments, calibration of models, .. were widely used. They are only achievable by clever approximation.
But this is not enough, patterns in data need to be evaluated efficiently to decide the best strategies ...
In short, speed matters.
