Er, markets are massively parallel, yes?
Um, am I wrong in thinking that P and NP refer to non-parallel algorithms?
(Apologies in advance if I'm having a brain fart.)
Markets are efficient if and only if P = NP (2010)
181–190 of 201 posts
Re: Markets are efficient if and only if P = NP (2010)
#182Earlier quoted context omitted.
Not really. It means that the market incorporates all past data. This paper is entertaining but it depends on the assumption that computing power grows exponentially forever and will eventually be able to solve all P problems at negligible cost. That assumption is clearly not justified. And the belief that any market perfectly incorporates data, not a single point off in any stock, is basically a strawman anyway.
I don't know! I'm wondering! Because weak-form efficient means something different than strong efficiency, which is what you say when the market perfectly incorporates all data. Just out of curiosity, if the data doesn't go into the market, where does it go? Strong econ minds believe that prices do incorporate all the data necessary for valuation
Sometimes data gets lost. People are making the decisions, and people are sloppy and lossy.
Weak and strong are just about which data is incorporated. Neither one addresses the fact that no entity interacting with a market is infallible.
Re: Markets are efficient if and only if P = NP (2010)
#183Earlier quoted context omitted.
Thanks, very charitable reading but doesn't work because next sentence I said that the new prime is larger than largest. As other poster points out if 2,7 are all your primes you produce 15, whose primes are not larger than 7 so the "new prime" wasn't referring to one of them. But that's not how I argued. Instead I showed that 15 is the new prime because it's relatively prime to all the primes. (By the assumption we…
Your post says "No prime divides the new number, so you've just produced a new prime." What, exactly, do you mean by "produced"? You say produced, not "established the existence of", so it makes it sound like you are assuming a constructive argument. Do you mean that the number you've produced is prime? Or do you mean that "the number you have computed is either prime or has a prime factors not in your list of primes…
Andrew, I perfectly see what you're saying, but I am telling you it is absolutely no problem that there's a false statement.
Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point.
One definition of a prime is that there are no primes smaller than it in its prime factorization. We'll call this definition NSPIPF - no smaller prime in prime factorization. Is NSPIPF an OK test for primality? Sure.
So when you get to new_number, produce the prime factorization. Does it meet the definition of NSPIPF? Yes, because we made it relatively prime to every prime (under assumption A).
It passes primality test NSPIPF. Under A. And therefore is prime. Under A. (This is the part you and others object to, but it's absolutely flawless application of the NSPIPF primality test.) It doesn't matter that in some other way I could also get to a contradiction. For now this is what we do.
Under A, using NSPIPF primality test, we just proved new_number is prime.
Next we show that this new_number definitely wasn't in the set of all primes, since it's larger than L, having had L and a bunch of other positive integers as factors and then one added to that for good measure. It is at this point that we show explicitly that A cannot be true, because we used A to produce a prime that wasn't in the set of all primes.
It doesn't matter if that was a false statement!
I think all this is in my original comment and it is a flawless proof by contradiction. I asked you to "Suppose there are just finite primes, up to some largest" and you gave up when you started seeing false statements, rather than at the end of the paragraph where I presented the conclusion in black and white.
Re: Markets are efficient if and only if P = NP (2010)
#184Earlier quoted context omitted.
On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a…
In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. IE, it is almost as good. So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough. Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin wit…
Markets don't need to be 99.9999% efficient either. Central planning can have a wide variance in efficiency. It could be substantially more efficient or extremely inefficient. If markets are able to reliably produce more efficiently year after year, even at the cost of lower peak-efficiency, then markets can still triumph in the long run.
Re: Markets are efficient if and only if P = NP (2010)
#185Earlier quoted context omitted.
Your post says "No prime divides the new number, so you've just produced a new prime." What, exactly, do you mean by "produced"? You say produced, not "established the existence of", so it makes it sound like you are assuming a constructive argument. Do you mean that the number you've produced is prime? Or do you mean that "the number you have computed is either prime or has a prime factors not in your list of primes…
Andrew, I perfectly see what you're saying, but I am telling you it is absolutely no problem that there's a false statement. Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point. One definition of a prime is th…
Nobody is contesting that the conclusion is true, just that the proof is unsound as written.
Here you've introduced a definition of prime that is different than the usual one, and is in fact self-recursive. NSPIPF is "no smaller prime in prime factorization". What is the first "prime" in this definition? Is it a number such that there is "no smaller prime in prime factorization"? What is the second "prime" in that definition? Is that the usual "prime factorization", or is it an NSPIPF factorization? In other words, how would you prove that 2 is prime given the NSPIPF definition?
It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself. That way we can make a precise statement about the product of the finite set of primes plus one without reference to the set of primes.
Re: Markets are efficient if and only if P = NP (2010)
#186Earlier quoted context omitted.
If you can show an inefficient market experimentally whenever you want, that's good enough to disprove EMH. The EMH doesn't say, "All information is normally factored into the price, except for technicalities." I like your drug trial example but a "hypothetical ideal expert" isn't assured to exist. Do you have an existence proof? On the other hand, unique prime factorization is assured, we know that given infinite ti…
The EMH is usually restricted to "available information". This hinges on what "available" means. I would argue that until the search space was reduced to the point where it would be feasible to factor the secret before another digit is revealed, the information is not "available" in any useful sense. So maybe, in some sense, this helps us narrow down a definition of what "available" means, but since real-world price…
100 possibilities are really easy to test, though, so P must be fully available near the end. We can all agree it's not available at the beginning (subject to the methodology.) So it becomes more and more available over time, but that is not what the EMH says -- at all. If you are saying market prices will reflect information as a function of how "readily" available it is (for example how smart you have to be to see it), that is just not EMH.
For the drug trial example, again, I like it but perhaps such an expert is theoretically excluded? Your statement might be like saying "suppose there's a hypothetical O(n) halting algorithm that answers the halting problem in constant time for the length of the program it's testing." That's nice but there's a proof that what you've just hypothesized is impossible[1].
I am not exactly saying that an ideal expert in human biochemistry who can predict the results of drug trials is impossible, but how do we know it's possible? I mean, is chemistry guaranteed to be fully computable or something?
For your last point, I think that what I asked to assume (that the $1B transfer is credible, that the computer is secure) are nowhere near the size of assumption of something like "assume there exists someone who can predict biochemical reactions in humans without testing." Basically the legal instruments and secure computers I included are easy, solved problems that I ask the reader to assume are being implemented following best practices.
Re: Markets are efficient if and only if P = NP (2010)
#187Earlier quoted context omitted.
Andrew, I perfectly see what you're saying, but I am telling you it is absolutely no problem that there's a false statement. Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point. One definition of a prime is th…
Nobody is contesting that the conclusion is true, just that the proof is unsound as written. Here you've introduced a definition of prime that is different than the usual one, and is in fact self-recursive. NSPIPF is "no smaller prime in prime factorization". What is the first "prime" in this definition? Is it a number such that there is "no smaller prime in prime factorization"? What is the second "prime" in that de…
>It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself
This is clearly not what I was doing. I clearly referred to having no smaller prime factors. Anyway this aside is tiresome, it's like poking me for saying "every positive integer has a prime factorization" and then asking, okay, so what about 1 or something. I think my proof is fine and I'm not going to defend it anymore.
Re: Markets are efficient if and only if P = NP (2010)
#188Earlier quoted context omitted.
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.
Then you must be doing something wrong. I, always, speak my mind. This sometimes backfires karma wise but on the long run i think it was minimal.
It's called having unpopular opinions.
That you're conventional enough to never stand out of the herd says more about you than anything else.
Re: Markets are efficient if and only if P = NP (2010)
#189Frankly, 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 Citation? True Scotsman fallacy?
So I actually opened Keen's book - and it's more damning than I remembered. He quotes evidence that two major proponents of EMH - Sharpe and Fama - have made very critical comments as to its (EMH) empirical validity.
Isn't it also ironic that you criticize the book as being pop-sci by perusing Wikipedia? You know, in both cases, being pop-sci doesn't imply being wrong.
Re: Markets are efficient if and only if P = NP (2010)
#190Earlier quoted context omitted.
When I tried to read about Allende's cybersyn all I could find are a few retro-futuristic furniture, but no meat whatsoever about the kind of software that was behind. It looked like pure PR to me. Do you have good sources about it? It has always intrigued me. Personally I think it is very unlikely that the markets are close to the best approximation we can afford. The current market-making agents use limited intelli…
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…
Thanks!