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

171–180 of 201 posts

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

#171

Post by myWindoonn »

babypistol wrote: post #169
myWindoonn wrote: post #161

Earlier quoted context omitted.

There is a reasonable-to-read paper [0] that explains everything; I will only share a few responses to your concerns. "Our puny brains" have no problem constructing O(n^100) or similarly-ridiculous problems. Here is an informal survey [1] of several good examples. In my previous message, I indicated that matrix multiplication and CFG parsing are good examples; they are both cubic-time but we have come up with even ch…

Thanks for the explanation. But, I do have some comments: 1) As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.) But here you are actually supporting my point: event in that case we could choose sufficiently sized keys. 2) And yes, the fact that P is s…

Last reply; the sun's up and work starts soon. I'm leaving breadcrumbs.

On RSA: You're right, but this is only the tip of the iceberg. There's a concept, "Impagliazzo's five worlds," which explains in fine detail how the various P!=NP and P=NP scenarios impact cryptography. Basically, whether P equals NP could be an easier question than another open question, whether one-way functions even exist. There are cryptographic practical implications.

On multiplication: You are correct that DTIME(n) ≤ DTIME(n^2). However, P = DTIME(n) + DTIME(n^2) + DTIME(n^3) + …

If you would like to consider that only some small sections of P are tractable, then that's an understandable stance to take. There is, as I've mentioned before, an entire subfield of computer science dedicated to trying to move matrix multiplication from DTIME(n^3) to DTIME(n^2).

On approximation: Integer programming is simply harder than approximation. That's all. The fact that the approximations are tractable doesn't slake our thirst for the precise answers. Moreover, we don't know how BPP and NP relate yet, so it could be that there are ways to solve problems exactly in NP by randomized algorithms. We've found a few hints at this already, but derandomization is a hard process. (We don't even know if BPP=P, although P≤BPP and BPP is self-low. The holy grail of derandomization would be to derandomize BPP to P.)

Finally, I really encourage you to take a bit of time to read the Aaronson paper I previously linked, because it explains all this in much more detail. You are free to continue to think that the problem is not interesting, but I encourage you to at least get a sense of why it is hard.

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

#172

Post by viraghr »

babypistol wrote: post #85
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…

I haven't heard of EMH before today and can't really comment on that. But it seems to me that even in the example from your note the stock price will tend to reflect the the correct price. As you realease new information the factorization becomes more feasible and once it's feasible enough the stock price will get the correct value. Maybe we should amend EMH to say that asset prices fully reflect all the facts that a…

Sure, but you can't "amend EMH" to fully reflect all the facts that are "feasible to compute" any more than you can amend it to say that that asset prices fully reflect the "best feasible analysis". That's not EMH.

For the prime proof, the new number is prime as long as as it has no prime factors < itself, which we assumed at the start. This guarantees it's prime under our assumption and this falsifies the assumption. Doesn't matter if it's really prime.

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

#173

Post by andrewla »

viraghr wrote: post #166
andrewla wrote: post #159

Earlier quoted context omitted.

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 actual…

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 signals are rarely something that is deterministically computable, I'm not sure that this would help to clarify the EMH.

In my drug trial example, such an expert does not exist, but if we're dealing with mundane real-world stuff, then the assurances that the proposed $1B gift to a random company would actually go through would have to be factored into any strategy -- why would I bother committing computing resources to factoring the number when in all likelihood the billion dollars would not handed over because why would anyone actually do that?

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

#174

Post by andrewla »

viraghr wrote: post #167
andrewla wrote: post #158

Earlier quoted context omitted.

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.

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, therefore, by computing the factorization of that number, you produce a new prime"?

The former statement is demonstrably false, the latter statement is true. Others have read your proof as stating the former, and I argue that the latter is a generous but not unreasonable interpretation of your phrasing.

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

#175

Post by csomar »

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.

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.

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

#176

Post by babypistol »

myWindoonn wrote: post #171
babypistol wrote: post #169

Earlier quoted context omitted.

Thanks for the explanation. But, I do have some comments: 1) As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.) But here you are actually supporting my point: event in that case we could choose sufficiently sized keys. 2) And yes, the fact that P is s…

Last reply; the sun's up and work starts soon. I'm leaving breadcrumbs. On RSA: You're right, but this is only the tip of the iceberg. There's a concept, "Impagliazzo's five worlds," which explains in fine detail how the various P!=NP and P=NP scenarios impact cryptography. Basically, whether P equals NP could be an easier question than another open question, whether one-way functions even exist . There are cryptogra…

I don't understand why you are responding to me in such a condescending tone, but thanks anyway for the discussion.

I'm well aware that P vs NP is a very hard question (I have studied quite some complexity theory, although I am a bit rusty), I'm saying that it does not seem as fundamental (or interesting) to computer science as people believe it to be.

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

#177

Post by wahern »

Iv wrote: post #87
zwww wrote: post #84

Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's c…

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…

The only book discussing the history of Project Cybersyn is, I think, Cybernetic Revolutionaries: Technology and Politics in Allende's Chile by Eden Medina. (https://www.amazon.com/dp/B006NY5426) Here's my Amazon review: https://www.amazon.com/gp/customer-reviews/R1IBPD2HGZ6UVA/

The project was very short-lived, but (IIRC) the primary designer was Stafford Beer (https://en.wikipedia.org/wiki/Stafford_Beer) who based the work on his so-called Viable System Model (https://en.wikipedia.org/wiki/Viable_system_model). For the fundamental theories of the time you'd want to read Beer's works as well as those of his contemporaries, who espoused competing theories and methodologies. (I say "at the time" but the state of the art never really changed. Project Cybersyn is a fascinating chapter in the long-history of AI, and if there's any dominate thread to AI it's one of diminishing expectations and migration to ever more circumscribed problem domains.)

As I mention in my Amazon review the author, Eden Medina, seems to have compiled a ridiculous amount of material but only a fraction of it bleeds through into her book. The book is fascinating but if you're interested in the theory and history more generally then the book's bibliography is priceless.

It's been awhile since I read the book but here's one lasting impression: one of the biggest problems with Project Cybersyn was communication between producers and consumers. Much of the budget and time was actually spent on telecommunications infrastructure and then figuring out how to get people to use it properly. Which hints at one of the most important functions of a market: price signaling. Regardless of whether a market is efficient, given the dynamic nature of a complex economy any system you setup that tries to centralize price signaling (capturing pricing information is a prerequisite for processing it and generating optimal allocations) seems like it'd very quickly become antiquated and a hindrance. Markets may be inefficient but at scale not only are they remarkably powerful distributed computation engines, they co-evolve with the economy. But that doesn't mean there isn't room for applying these techniques in sub-domains (e.g. trading engines, city governance, etc), improving overall efficiency.

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

#178

Post by stale2002 »

SolarNet wrote: post #53
stale2002 wrote: post #47

Earlier quoted context omitted.

Equal number of people doesn't not solve the principle agent problem. The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves. Markets are currently the way that puts the maximum amount of control into each individuals own hands. IE, a person has X resources, and they can trade them how they like because they are best able to under…

> The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves. I don't see how markets are supposed to solve that when we allow countries with slaves to participate on the markets. Or landlords to exercise economic rent over the land that other people maintain and live on. I guess my point here is I'm not sure markets as we have them t…

Equal number of people doesn't solve the problem. It has to be the SAME people, working in exactly the same way to make decisions for themselves. IE, you just recreated a market.

An equivalent system would have to have the same people, in control of their own resources.

If you just replace the people who are currently making decisions about themselves, with DIFFERENT people, them the principle agent is no longer making decisions for themselves. A different person is making thise decisions for OTHER people, which is the principle agent problem.

Surveys and computer generated questions sounds an aweful lot like other people making decisions over other people's utility functions and resources. IE, they are not the principle agent.

You'd have to prove that surveys or whatever are better at deciding what a person wants than the person themself.

Even if you have more resources, it is still different resources. It is still different people making decisions for what other people want.

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

#179

Post by stale2002 »

coldtea wrote: post #46
stale2002 wrote: post #41

Earlier quoted context omitted.

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…

> In economics, the difference between "efficient market" and "epsilon away from efficient" is very little. In economics, yes. In real life, not so much.

For utilty functions?

Why not?

IE, if a person is only 1$ poorer than the efficient solution, that's not a big deal.

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

#180

Post by Isinlor »

yoklov wrote: post #71
mortdeus wrote: post #66

So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition? In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart al…

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…

From "TRAINING A 3-NODE NEURAL NETWORK IS NP-COMPLETE":

We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for the three nodes of this network so that it will produce output consistent with a given set of training examples.

https://papers.nips.cc/paper/125-training-a-3-node-neural-ne...

Post reply on HN