7 ms·

How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the gen

How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes?

na85 6y ago
Well what I think is interesting as an amateur with an interest in economics and investing, is that if P!=NP then it would cast a great deal of doubt on so-called Technical Market Analysis or "Technicals" which are predicated on the Efficient Market Hypothesis being true. My own suspicions have been for quite some time now that fundamentals are what move markets and that technicals are mostly bullshit and are only valid because algo-traders school like fish based on technicals.
- whoisburbansky 6y ago
  The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information; "the market can remain irrational longer than you can stay solvent." It's the sort of thing that's hard to falsify because you can always say "oh, it'll eventually become consistent." Given that, I don't think this fundamentally changes anything about "technicals," even if P!=NP, but my intuition a priori is also the same as yours, that "technicals" are mostly window dressing anyways.
  - na85 6y ago
    >The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information Actually it does. The central premise of the Efficient Market Hypothesis is that all relevant information is already priced in. >"the market can remain irrational longer than you can stay solvent." Irrational behaviour by uninformed investors is theoretically already priced in, if the market is efficient.
    - whoisburbansky 6y ago
      Taking that literally, it's clearly false; information can't affect prices faster than the speed of light.
      - na85 6y ago
        Ah yes the good ol' HN pedantry. Please go actually read the hypothesis and understand its central tenets.
        jabl 6y ago
        Ah, but here's an interesting topic for an ambitious research project, "Efficient relativistic markets". The proposal would score cross-disciplinarity brownie points in the evaluation committee.
        hchasestevens 6y ago
        You might be surprised to learn that the well-known economist Paul Krugman wrote in the late 70s about trade in relativistic scenarios, see https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Trade https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Tra... and http://www.standupeconomist.com/pdf/misc/interstellar.pdf http://www.standupeconomist.com/pdf/misc/interstellar.pdf (for the paper itself).
        jabl 6y ago
        Ah, but of course. When you're not a subject matter expert what you think is a novel idea is something the actual experts have already investigated decades ago. sigh, oh well.
        bawolff 6y ago
        We're literally talking about a paper comparing emh to np=p, isn't pointless pedantry the name of the game?
    - rocqua 6y ago
- akra 6y ago
  I thought technical analysis (as opposed to fundamental analysis) assumes markets aren't efficient and subject to things like herd behavior and other psychological effects of human decision making. Otherwise things like momentum trading wouldn't work (i.e. price would just gap to the true value if markets were indeed efficient). If tech analysis works at times for me it would show that markets aren't that efficient as a whole. IMO markets can't be efficient because we as humans aren't - our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.
  - bo1024 6y ago
    > our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc. The intuition behind the efficient market hypothesis is that each of these deviations from "homo economicus", if it occurs in a market, is an opportunity for someone else to make money. EMH says that opportunity won't be wasted, at least for very long.
    - kohlerm 6y ago
      That still means efficiency is lost. E.g. the market might fluctuate between non-optimal state. And then again in case monopolies build up, then there is no easy way to get out of a suboptimal state, because there are no real opportunities for someone else.
- shawnz 6y ago
  Technical analysis doesn't depend on EMH being true, in fact it depends on EMH being false. It is not evidence based in any way.
klyrs 6y ago
The first corollary that I see is that greedy algorithms will almost certainly suck for society at large. I'm looking specifically at the meme that public companies are somehow required to maximize short-term profits for their shareholders. Some NP-complete problem classes have polynomial time approximation schemes, but not all, unless P=NP. That is to say, sufficiently large markets may be arbitrarily inefficient. I'm curious to see that dichotomy resolved.
- whoisburbansky 6y ago
  In every case of problems classes I have seen, in my admittedly limited experience, polynomial time approximation schemes only fail under pathological circumstances. I'm not convinced that there's a connection between pathological problem instances and problem sizes, necessarily, and I'm even less convinced that real-world markets would reflect such pathological instances.
  - klyrs 6y ago
    Granted, but such a PTAS would need to be agreed upon and faithfully executed by all market players.
- unishark 6y ago
  Greedy algorithms suck compared to what? If the greedy algorithm still converges fastest and is closest to optimal compared to any other practical scheme, the paper's result still does not say anything of practical use.
  - klyrs 6y ago
    They suck at escaping local minima, for one. Your "if" is doing a ton of work there, and this paper is quite abstract market theory. The "practical use" is to better contextualize the efficient market hypothesis.
    - unishark 6y ago
      They don't escape local minimum at all. And that means they suck for society at large compared to what? Random guessing? A corrupt government price system? An omniscient one that can solve NP hard problems? The "if" motivates answering the question. Anyway markets have a lot more going on than a simple greedy algorithm. For injecting noise into the optimization to get out of local minima. Markets clearly have a lot of this.
adrianN 6y ago
Well given that this assumes rational actors and humans aren't really rational, it's probably not very important in practice.
coldtea 6y ago
>How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes? Well, define "well enough"... We do get results. Are they "well enough"?
sacado2 6y ago
Even better, in practice we have amazing tools nowadays that can solve practical NP complete problems in a reasonable amount of time (I mean, optimal solutions, not OK-ish ones).

na85 6y ago

Well what I think is interesting as an amateur with an interest in economics and investing, is that if P!=NP then it would cast a great deal of doubt on so-called Technical Market Analysis or "Technicals" which are predicated on the Efficient Market Hypothesis being true. My own suspicions have been for quite some time now that fundamentals are what move markets and that technicals are mostly bullshit and are only valid because algo-traders school like fish based on technicals.

whoisburbansky 6y ago
The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information; "the market can remain irrational longer than you can stay solvent." It's the sort of thing that's hard to falsify because you can always say "oh, it'll eventually become consistent." Given that, I don't think this fundamentally changes anything about "technicals," even if P!=NP, but my intuition a priori is also the same as yours, that "technicals" are mostly window dressing anyways.
- na85 6y ago
  >The efficient market hypothesis doesn't say anything about the amount of time it might take for markets to iron out inconsistencies and take into account new information Actually it does. The central premise of the Efficient Market Hypothesis is that all relevant information is already priced in. >"the market can remain irrational longer than you can stay solvent." Irrational behaviour by uninformed investors is theoretically already priced in, if the market is efficient.
  - whoisburbansky 6y ago
    Taking that literally, it's clearly false; information can't affect prices faster than the speed of light.
    - na85 6y ago
      Ah yes the good ol' HN pedantry. Please go actually read the hypothesis and understand its central tenets.
      - jabl 6y ago
        Ah, but here's an interesting topic for an ambitious research project, "Efficient relativistic markets". The proposal would score cross-disciplinarity brownie points in the evaluation committee.
        hchasestevens 6y ago
        You might be surprised to learn that the well-known economist Paul Krugman wrote in the late 70s about trade in relativistic scenarios, see https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Trade https://en.wikipedia.org/wiki/The_Theory_of_Interstellar_Tra... and http://www.standupeconomist.com/pdf/misc/interstellar.pdf http://www.standupeconomist.com/pdf/misc/interstellar.pdf (for the paper itself).
        jabl 6y ago
        Ah, but of course. When you're not a subject matter expert what you think is a novel idea is something the actual experts have already investigated decades ago. sigh, oh well.
      - bawolff 6y ago
        We're literally talking about a paper comparing emh to np=p, isn't pointless pedantry the name of the game?
  - rocqua 6y ago
akra 6y ago
I thought technical analysis (as opposed to fundamental analysis) assumes markets aren't efficient and subject to things like herd behavior and other psychological effects of human decision making. Otherwise things like momentum trading wouldn't work (i.e. price would just gap to the true value if markets were indeed efficient). If tech analysis works at times for me it would show that markets aren't that efficient as a whole. IMO markets can't be efficient because we as humans aren't - our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.
- bo1024 6y ago
  > our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc. The intuition behind the efficient market hypothesis is that each of these deviations from "homo economicus", if it occurs in a market, is an opportunity for someone else to make money. EMH says that opportunity won't be wasted, at least for very long.
  - kohlerm 6y ago
    That still means efficiency is lost. E.g. the market might fluctuate between non-optimal state. And then again in case monopolies build up, then there is no easy way to get out of a suboptimal state, because there are no real opportunities for someone else.
shawnz 6y ago
Technical analysis doesn't depend on EMH being true, in fact it depends on EMH being false. It is not evidence based in any way.

klyrs 6y ago

The first corollary that I see is that greedy algorithms will almost certainly suck for society at large. I'm looking specifically at the meme that public companies are somehow required to maximize short-term profits for their shareholders. Some NP-complete problem classes have polynomial time approximation schemes, but not all, unless P=NP. That is to say, sufficiently large markets may be arbitrarily inefficient. I'm curious to see that dichotomy resolved.

whoisburbansky 6y ago
In every case of problems classes I have seen, in my admittedly limited experience, polynomial time approximation schemes only fail under pathological circumstances. I'm not convinced that there's a connection between pathological problem instances and problem sizes, necessarily, and I'm even less convinced that real-world markets would reflect such pathological instances.
- klyrs 6y ago
  Granted, but such a PTAS would need to be agreed upon and faithfully executed by all market players.
unishark 6y ago
Greedy algorithms suck compared to what? If the greedy algorithm still converges fastest and is closest to optimal compared to any other practical scheme, the paper's result still does not say anything of practical use.
- klyrs 6y ago
  They suck at escaping local minima, for one. Your "if" is doing a ton of work there, and this paper is quite abstract market theory. The "practical use" is to better contextualize the efficient market hypothesis.
  - unishark 6y ago
    They don't escape local minimum at all. And that means they suck for society at large compared to what? Random guessing? A corrupt government price system? An omniscient one that can solve NP hard problems? The "if" motivates answering the question. Anyway markets have a lot more going on than a simple greedy algorithm. For injecting noise into the optimization to get out of local minima. Markets clearly have a lot of this.

adrianN 6y ago

Well given that this assumes rational actors and humans aren't really rational, it's probably not very important in practice.

coldtea 6y ago

>How much does this matter given that in the vast majority of cases, we don't care about exact/perfect solutions to problems that might be NP complete in the general case, but usually have heuristic methods that work well enough for most practical purposes? Well, define "well enough"... We do get results. Are they "well enough"?

sacado2 6y ago

Even better, in practice we have amazing tools nowadays that can solve practical NP complete problems in a reasonable amount of time (I mean, optimal solutions, not OK-ish ones).