Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Markets are efficient if and only if P = NP (2010)

arxiv.org

Post reply on HN
Print view View original

101–110 of 201 posts

Re: Markets are efficient if and only if P = NP (2010)

#101

Post by cimmanom »

yellowstuff wrote: post #99
ianai wrote: post #60

Earlier quoted context omitted.

I don’t think economists claim markets are efficient. There’s far too many examples to the contrary - see amazon, wellsfargo, and Verizon as examples. While those companies do technically have competition, they operate with significant market power. Also, I once heard an Econ explain EH as “true if enough people operate under the assumption that it is not true” Edit-After waking up a little more, I’m not entirely sur…

The efficient market theory is that all information, public and private, is incorporated into all stock prices at all times, so there's no point to researching companies to try to outperform the stock market. I don't think anyone believes it is literally true, just that it is a good model for most stocks most of the time. If everyone believed it then no one would bother to research stocks, and the markets would be le…

That's a far more limited claim. There's a very common claim that "markets are efficient". Extending to all markets all the time. Explaining why market based solutions are the best way to provide health care and education and other (arguably common) goods.

But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and private information all or most of the time.

Re: Markets are efficient if and only if P = NP (2010)

#102

Post by leereeves »

babypistol wrote: post #97

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me. But in the article, t…

That's assuming computational resources could grow forever without limit, which of course they can't.

Re: Markets are efficient if and only if P = NP (2010)

#103

Post by captainbland »

Yuioup wrote: post #16

Can't markets just assume that it is and move on. It's not like markets never do speculation /s

This is bad news for the technology business when those markets only 'efficiently' allocate capital to companies that attempt to exploit P=NP.

Re: Markets are efficient if and only if P = NP (2010)

#104

Post by jonathanstrange »

ernst_klim wrote: post #89
jonathanstrange wrote: post #74

Earlier quoted context omitted.

Since when do mathematical limitations not apply to the real world? Have you ever tried to square the circle?

Let's start with the fact that circles do not exist in the real world.

Well, that's a quite insubstantial point, to say the least. Mathematical theorems place upper and lower bounds on what is possible in the real world within almost every domain. Of course, there may often be other reasons why something is impossible, too.

Re: Markets are efficient if and only if P = NP (2010)

#105

Post by QML »

MaysonL wrote: post #39

Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.

Not really.

Computational complexity and markets have more in common that most think. Mechanisms which rely on algorithms, such on auctions, have runtimes.

Hence, why we have a field called algorithmic game theory [1].

[1] https://en.wikipedia.org/wiki/Algorithmic_game_theory

Re: Markets are efficient if and only if P = NP (2010)

#106

Post by QML »

leereeves wrote: post #102
babypistol wrote: post #97

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me. But in the article, t…

That's assuming computational resources could grow forever without limit, which of course they can't.

To add on: Moore's law is "dying", and that places further pressure on algorithms to get faster.

However, even in an exponential world, I am reminded of a quote:

"exponential algorithms make polynomially slow progress, while polynomial algorithms advance exponentially fast".

Re: Markets are efficient if and only if P = NP (2010)

#107

Post by zmk_ »

cimmanom wrote: post #101
yellowstuff wrote: post #99

Earlier quoted context omitted.

The efficient market theory is that all information, public and private, is incorporated into all stock prices at all times, so there's no point to researching companies to try to outperform the stock market. I don't think anyone believes it is literally true, just that it is a good model for most stocks most of the time. If everyone believed it then no one would bother to research stocks, and the markets would be le…

That's a far more limited claim. There's a very common claim that "markets are efficient". Extending to all markets all the time. Explaining why market based solutions are the best way to provide health care and education and other (arguably common) goods. But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and priva…

EMH that this paper refers to is about financial markets. In other areas of econ, no one is claiming that markets are efficient, in fact most of econ talks about "first best", "second best", "losses in efficiency", etc.

Re: Markets are efficient if and only if P = NP (2010)

#108

Post by babypistol »

leereeves wrote: post #102
babypistol wrote: post #97

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me. But in the article, t…

That's assuming computational resources could grow forever without limit, which of course they can't.

Yeah, in this case we are back to square one and P vs NP again seems irrelevant to me.

Re: Markets are efficient if and only if P = NP (2010)

#109

Post by detaro »

mortdeus wrote: post #82
yoklov wrote: post #71

Earlier quoted context omitted.

No, I don't think building a neural net for image recognition qualifies. NP problems are essentially problems where the following two properties hold: 1. No better algorithm is known than using brute force -- generating every possible result and checking if it's a valid result. 2. Checking that the given result is valid is doable in polynomial time or better. (This is less critical to understanding, but essentially y…

but trying to devise a program that can predict somebody's password without using brute force is a NP problem? Since its hard to discover what the password is, but trivial to check if it lets you in the vault? I get the reasoning why people aren't sure if P = NP. Here is another question. What defines time? And what about a solution? Consider the fact that in the theory of general relativity we have the twin paradox.…

> According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.

No, since it can only save a constant factor of time. (Also, dragging random physics into a mathematical model based on a different view of the world isn't really helpful to understanding it. "Time" is computational steps, not seconds)

Re: Markets are efficient if and only if P = NP (2010)

#110

Post by csomar »

zeth___ wrote: post #79
csomar wrote: post #73

Earlier quoted context omitted.

> Have another account here but don't want to take the karma hit for being a crank. Stop worrying about karma and what some random dudes think about you/your comments on HN or whatever online board. If you think it is wrong simply don't do it.

You get silenced by karma when you have unpopular opinions. You know, just how people used to tell homosexuals to not be gay when other people thought they were freaks because of it.

What I’m saying is stop worrying about karma and talk your opinions. Karma is not money or air. Your opinion matters.
Post reply on HN