EMH <==> P=NP

I recently found this: Phil Maymin at TEDxNSIT

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.
In general the P versus NP complexity problem in computer science is unsolved.

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.