This paper's claim that finding an effective technical trading strategy is in NP relies on the search space for technical strategies being exponential in the length of history being considered (which it's not -- that's the size of a description of a single strategy) and the tacit assumption that historic performance of a strategy guarantees future performance.

Because of the assumption of there being a correct answer. It is as much a problem of definitions and arbitary valuation as anything.

An academic analysis like what you linked to has to assume everybody have settled on the same definitions and valuations.

That's true of all analysis. We can't even calculate 1 + 1 if we are not going to agree to the definition of the plus sign.

See my other comment describing what a perfect answer looks like.

There's a good argument to be made, that doing the market is harder than NP.