4 ms·

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

by 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?
- leelin 17y ago
  Maybe you've ever seen the cool proof that "Tetris is NP-complete". I loved the paper and it was very entertaining. But it involved a much broader and general Tetris problem than the one found in Nintendo Gameboys, because the width and the height of the pit in the reduction was larger than all the console based tetris games I've ever seen. 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.
  - pohl 17y ago
    I think I'm following now. You're saying that the author is assuming a model of economies that is more complex than an actual economy. That could be the first time ever that I've heard such a thing about any model, let alone of an economy. :-) 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.

by leelin 17y ago

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?

leelin 17y ago
Maybe you've ever seen the cool proof that "Tetris is NP-complete". I loved the paper and it was very entertaining. But it involved a much broader and general Tetris problem than the one found in Nintendo Gameboys, because the width and the height of the pit in the reduction was larger than all the console based tetris games I've ever seen. 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.
- pohl 17y ago
  I think I'm following now. You're saying that the author is assuming a model of economies that is more complex than an actual economy. That could be the first time ever that I've heard such a thing about any model, let alone of an economy. :-) 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.