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

151–160 of 201 posts

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

#151

Post by Thiez »

TekMol wrote: post #112
js8 wrote: post #61

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that a…

Frankly, everybody with a bit of economic common sense knows Said every hot headed teenager with an attention span too short to think through scientific arguments.

If you want to do the 'scientific arguments' thing, then surely it is up to the EMH proponents to convince the rest of us, while the rest of us stick to the null hypothesis.

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

#152

Post by openasocket »

lynal wrote: post #146

Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it's helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results. That's the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficie…

> Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement?

It actually does have a formal meaning! This is one of the most interesting results (in my opinion) on the P vs NP problem. Given a random oracle R, Pr(P^R != NP^R) = 1. So given a random universe, it is almost certainly true that your version of P != your version of NP. At least that's how my theory prof liked to explain it.

Here's a link with the proof: http://theory.stanford.edu/~trevisan/cs254-14/lecture04.pdf

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

#153

Post by js8 »

heavenlyblue wrote: post #144
js8 wrote: post #61

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that a…

EMH is supported by the existence of Index Funds. So the truth of EMH depends on any point in time where the answer to the question of "Do Index Funds on average earn more than Private Funds?" is yes. It's not even binary and is not a static property, just like our laws are just a proxy to a question of what is ethical or moral; and the truth of their purpose is entirely based on the historical context.

I am not sure I understand. If EMH was true, they should perform the same, no?

I would argue that belief in EMH is supported by existence of index funds. But index funds are also supported by laws that require certain level of openness and information sharing (such as laws against insider trading). When this information sharing is not enforced by law, it is a major source of market inefficiencies.

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

#154

Post by bluGill »

heavenlyblue wrote: post #144
js8 wrote: post #61

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world. If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH. Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that a…

EMH is supported by the existence of Index Funds. So the truth of EMH depends on any point in time where the answer to the question of "Do Index Funds on average earn more than Private Funds?" is yes. It's not even binary and is not a static property, just like our laws are just a proxy to a question of what is ethical or moral; and the truth of their purpose is entirely based on the historical context.

Not really. Index funds depend on the markets being efficient enough that the cost of finding the inefficiencies is higher than the gain from finding them. The more people who blindly invest in markets, the less efficient the market is in reality, and the more possible gain for those who do research.

Note that I said "people invest in markets", and not index funds above. There is a subtle differences, modern index funds are not true market indexes. There are fund managers who trade actively - however they trade mush less often than a traditional actively managed funds and with different rules. The managers do watch earnings reports and sell bad stocks, but the managers are also in for the long term and re willing to wait out a downturn. The managers also know they are judged by the index, and so bad stocks are not a negative in the same way that active funds are judged. Thus an index fund trades much less often, but they are not really a buy the index as published.

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

#155

Post by babypistol »

myWindoonn wrote: post #149
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…

No. The reason why computation in P is considered tractable is because the exponents in polynomial coefficients in complexity analyses tend to be small. Linear-, quadratic-, and cubic-time algorithms dominate P, and we pride ourselves on finding ways to reduce those exponents. Some problems in P, like matrix multiplication and context-free parsing, have been analyzed to death this way. We give importance to this ques…

Well I'm trying to understand why this question is big.

The fact that the exponents tend to be small in the algorithms that our puny brains were able to produce does not convince me one bit that all problems in P have algorithms with small exponents.

Why are you so sure that P vs NP is important? Does it really relate to so many parts of computer science?

I do agree that complexity analysis is a very (perhaps the most) important part of CS. But that does not necessarily mean that P vs NP is a fundamental question.

RSA wouldn't break even if P = NP. Even if we came up with a polynomial algorithm for integer factorisation in could have a much higher exponent than the multiplication required to verify the result.

This is what bothers me the most, people saying that P = NP implies that solving a problem is as difficult as verifying a solution. That's simply not true: P = NP implies that solving a problem is as difficult as verifying a solution (modulo polynomial reductions).

The part about ignoring polynomial reductions seems very important to me. Otherwise I could also say that: "all even numbers are the same", when I actually mean: "all even numbers are the same (modulo 2)".

Would you care to convince me why we chose to ignore polynomial reductions and not some other complexity class?

The best explanation I see is the fact that different Turing machine formulations (single-tape, multi-tape, one-way infinite, two-way infinite, ...) and also the random access machines have polynomial reductions between them. But even this does not justify the importance we give to P vs NP in my eyes.

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

#156

Post by baursak »

rileyphone wrote: post #150
baursak wrote: post #122

Earlier quoted context omitted.

I'm interested in this. So far, the best resources I found are: - "Red Plenty" by Francis Spufford, a mix of fiction and non-fiction about planning experience in the USSR. It includes a rich bibliography and references to papers published over the past 70 years around this issue. - There are few papers by Chinese economists, most notably this one: https://boingboing.net/2017/09/14/platform-socialism.html (you have to…

Check out "Towards a New Socialism", by the aforementioned Cockshott and Cotrell. Cockshott himself is a computer scientist and proposes planning the economy based on solving a linear system of labour inputs.

Ah, yes, forgot to mention them. I haven't read the book yet, but read some of their papers, yes those are good too.

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

#157

Post by Ar-Curunir »

babypistol wrote: post #88
Ar-Curunir wrote: post #23

Earlier quoted context omitted.

> I'm not sure I understand the author's implication that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.

In my opinion P = NP does not mean that. There still might be a big polynomial difference between verifying a solution and finding one.

Of course, the concrete costs can be different; I was talking asymptotically :)

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

#158

Post by andrewla »

ayepif wrote: post #86
viraghr wrote: post #57

Have another account here but don't want to take the karma hit for being a crank. I published this 2-page proof that the EMH is false: https://arxiv.org/abs/1011.0423 (didn't set the date so in the document it's wrong, this was published 2010.) It doesn't depend on P = NP, it's simply a rigorous proof that EMH is false. Let's switch gears a second. Here's a famous elementary proof[1] that there are infinite primes. S…

Maybe I'm being super pedantic and possibly confrontational (I apologise in advance) but it jumped out on me here. I think you've misunderstood the 'famous elementary proof' that there are infinite primes. You do not create a new prime as you have suggested (quoted below). "Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new p…

Technically, the parent post literally said "No prime divides the new number ... so you've just produced a new prime". It does not make the direct claim that the new prime is equal to the new number.

It is possible that the OP did not make the mistake that you are attributing to them, although best case is that the exposition was simply unclear.

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

#159

Post by andrewla »

viraghr wrote: post #57

Have another account here but don't want to take the karma hit for being a crank. I published this 2-page proof that the EMH is false: https://arxiv.org/abs/1011.0423 (didn't set the date so in the document it's wrong, this was published 2010.) It doesn't depend on P = NP, it's simply a rigorous proof that EMH is false. Let's switch gears a second. Here's a famous elementary proof[1] that there are infinite primes. S…

Your proof for the EMH hinges on a very specific technicality -- whether the secret prime, P, is public knowledge, or to what degree it is public knowledge.

I think if we were to approach the EMH from a constructive or computability approach, we'd have to make that definition much crisper. That is, the feasibility of computing the factorization based on limited information determines whether the information is actually "available" in the sense of the EMH.

In the real world we can see things like drug trials that will determine the success of a pharmaceutical company. The information that the drug works or doesn't work, or has side effects, would be "apparent" to a hypothetical "ideal" expert in human biochemistry -- so simply knowing the chemical formula for a new drug, the information about its working is "available" in that sense.

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

#160

Post by [deleted] »

zeth___ wrote: post #142
csomar wrote: post #110

Earlier quoted context omitted.

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

And what I'm saying is that you literally can't when you get enough negative karma. I have three HN accounts and two of them have negative karma and can't post without mod approval. Or it just says: You're posting too fast. Please slow down. Thanks.

[deleted]
Post reply on HN