There's also a fairly trivial argument for the incomputability of the EMH: for each Turing machine, issue bonds that compound interest in perpetuity and pay it off if the Turing machine halts. Since the value of the bond is positive if the Turing machine halts and zero if it doesn't, in an efficient market investors will price the bonds in a way that solves the halting problem.
Forgive me if I'm not understanding what you're getting at here. (I haven't read the paper). But, on first blush, it appears that 3-SAT is not mentioned for the purpose of analogy, but rather for use as a standard "reduction" (in the parlance of NP-Completeness proofs), in which case reducing to any NP-Complete problem is as good as reducing to any other. They're typically only chosen by whether they are amenable to some poly-time transformation, aren't they?
It's been a long time since I've had my course in this, so caveat emptor.
More importantly, I'm calling out the author's representation as bogus. He proves that anyone who represents the markets his way is trying to solve an NP-complete problem, and that given the problem is NP-complete the hedge funds and banks can't possibly have computed the solution.
(While I don't feel qualified to verify the correctness of the author's reduction, the form of the proof feels like any other that I've read.)
...but the author's big leap of faith is that our particular one case of the problem is intractable.
What does "our particular one case of the problem" mean? Do you mean a particular case of the 3-SAT problem?
If so, reductions don't consider a particular case of 3-SAT (or whatever known NP-Complete problem type one is using for leverage). Rather, they transform any arbitrary 3-SAT problem statement, in poly time, into an equivalent statement in the problem domain under consideration. By showing a transformation of any arbitrary problem, it covers all 3-SAT cases: trivial and intractable. All possible problem statements thus covered, no leap of faith is required.
If not, what sort of problem (and particular case thereof) are you referring to?
My understanding is that Gameboy tetris, given the sequence of all future blocks as input and an empty pit starting state, is actually easy to solve computationally.
Similarly, I have to believe that the market as we know it contains some constraints, and all the historical data will abide by those constraints. To show the market problem is NP-hard, you would need all 3-SAT reductions to lead to a valid market problem. Going back to Tetris, IIRC, a large number of the reductions would lead to Tetris games that could not exist on Gameboy Tetris, because you would need a block-pit that is far taller than the game allows.
The only assumption that I see him making is the weak form of the Efficient Market Hypothesis.
I'm curious...how do you feel about that hypothesis, anyway? I've thought the EMH was a pretty strange and obviously false hypothesis ever since I first heard of it in the 80s (in college).
Just look at this statement from the Wikipedia page on the subject: It is the assumption "...that prices on traded assets already reflect all available information, and instantly change to reflect new information." This is a flimsy foundation to build on, because it's assuming the instantaneous propagation of information between economic actors. By what mechanism? Quantum entanglement? Crazy action at a distance?
I realize it was probably first intended in the same way that one uses a point-mass in physics ("we know it can't exist, but it makes the math easier") but I don't think it's quite as harmless as that.
Anyway, I'm happy to see the author taking such a clever swing at it.
A.) First several pages are random fluff: Explains P, NP, NP-Hard, NP-Complete, history of P=NP, examples of NP-complete problems, examples of market efficiency, and other very uninteresting stuff that feels like it's trying to fill out pages.
B.) Makes this central argument:
1.) If markets are efficient, then no one can come up with a consistently profitable trading strategy based on analyzing historical data.
2.) Model historical data as a sequence of days where the market can go up or down on any given day.
3.) Model a trading strategy as being long, short, or neutral the market on any given day, to be started after recognizing some pattern for the previous N days.
4.) To determine from historical data whether a profitable strategy exists, you'd need to try all combinations of being long, short, or neutral over some time horizon, while looking for all market patterns. Trying all such combinations is O(3^N) or O(2^N), depending on whether you believe the expensive part is finding the strategy or finding the pattern.
5.) To verify that you have a winning strategy, you merely need to simulate the strategy over your historical data, which only takes O(N).
6.) Therefore, it is in NP. Similarly, it is NP-Hard because we can reduce 3-SAT to a market / trading problem. Therefore, "does a profitable strategy based on historical data exist?" is in NP-complete.
7.) Because our model shows finding the existence of a profitable strategy is NP-complete, then either P=NP or markets are inefficient.
C.) A few comments of my own:
1.) Suppose we believe the argument. The amount of historical data is finite, so maybe some hedge funds brute-forced a solution and removed the market inefficiencies they've found.
2.) I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking. A* search on a landscape with reliable heuristics might be a better analogy. In trading markets, you don't need to try all 3^N combinations because just as in search algorithms, you have heuristics that can help prune large parts of your search space (if a strategy starts off losing money, no need to keep exploring all the 3^N combinations under it).
3.) The author assumes everyone represents and models the market his way. Maybe a more clever representation makes the problem tractable. Checkers is a solved game now, even though there are in theory infinitely many possible game histories to test.