4 ms·

Summary of paper: A.) First several pages are random fluff: Explains P, NP, NP-Hard, NP-Complete, history of P=NP, examples of NP-complete problems, examples

by leelin 17y ago

Summary of paper: 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.

jplewicke 17y ago
When I first saw the headline, I assumed it was going to be about the CDO packing problem discussed at http://rjlipton.wordpress.com/2009/10/22/helping-wall-street-cheat-with-theory/ http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... . The basic idea is that if you're buying a Collateralized Debt Obligation, you can't tell whether the people structuring the deal have intentionally given you an unfair share of bad loans, even when you know a lot about each of the loans in particular. 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.
- aprime 17y ago
  Doesn't this only prove that there cannot be an efficient market for these special "Turing machine" bonds?
  - jplewicke 17y ago
    That's definitely true. It's only a counterproof to some extremely strong versions of the EMH that assume that you can buy any possible asset or derivative. http://en.wikipedia.org/wiki/Complete_market http://en.wikipedia.org/wiki/Complete_market
pohl 17y ago
I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking. 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.
- leelin 17y ago
  You are correct, but the author's big leap of faith is that our particular one case of the problem is intractable. I'm claiming the reduction from 3-SAT to his market problem is likely broken because the general market problem is subject to at least some additional constraints for it to reflect our reality. For example, you can't have MSFT stock rapidly alternating from $10 to $200 every day, which might be what happens during your 3-SAT reduction. 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.
  - pohl 17y ago
    I've read the paper now, and I'm still a little confused by the way that you have phrased your objections. More specifically, I don't understand how the form of your objections could constitute a valid criticism of any NP-Completeness proof whatsoever. (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?

by leelin 17y ago

jplewicke 17y ago

When I first saw the headline, I assumed it was going to be about the CDO packing problem discussed at http://rjlipton.wordpress.com/2009/10/22/helping-wall-street-cheat-with-theory/ http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... . The basic idea is that if you're buying a Collateralized Debt Obligation, you can't tell whether the people structuring the deal have intentionally given you an unfair share of bad loans, even when you know a lot about each of the loans in particular. 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.

aprime 17y ago
Doesn't this only prove that there cannot be an efficient market for these special "Turing machine" bonds?
- jplewicke 17y ago
  That's definitely true. It's only a counterproof to some extremely strong versions of the EMH that assume that you can buy any possible asset or derivative. http://en.wikipedia.org/wiki/Complete_market http://en.wikipedia.org/wiki/Complete_market

pohl 17y ago

I think SAT and travelling salesman are the wrong analogies, because solving both optimally can involve lots of backtracking. 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.

leelin 17y ago
You are correct, but the author's big leap of faith is that our particular one case of the problem is intractable. I'm claiming the reduction from 3-SAT to his market problem is likely broken because the general market problem is subject to at least some additional constraints for it to reflect our reality. For example, you can't have MSFT stock rapidly alternating from $10 to $200 every day, which might be what happens during your 3-SAT reduction. 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.
- pohl 17y ago
  I've read the paper now, and I'm still a little confused by the way that you have phrased your objections. More specifically, I don't understand how the form of your objections could constitute a valid criticism of any NP-Completeness proof whatsoever. (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?