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

91–100 of 201 posts

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

#91

Post by n4r9 »

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…

You're entirely correct. A very ironic mistake/misunderstanding for the parent post to make.

Edit: I've thought about this a bit more, and you can save the parent post by prepending a result like "Every number larger than one is either prime, or divisible by a prime smaller than itself". In this case you can then assert that your constructed number is prime. However, this result requires its own proof and was not mentioned by the parent post.

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

#92

Post by zaarn »

mortdeus wrote: post #83
zaarn wrote: post #77

Earlier quoted context omitted.

Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend. A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretati…

I've read a little bit about turing machines and there is also a variation that includes what is called an "oracle" machine. Do you know anything about that?

An oracle machine is usually a turing machine that can tell you things about other turing machines.

An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)

A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.

Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).

Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).

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

#93

Post by psergeant »

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

Citation? True Scotsman fallacy?

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

#95

Post by bigleagueposter »

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…

Fuzzy analogies will get you nowhere.

> And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data

No it's not. You can't do reasoning on bullshit inaccurate analogies.

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

#96

Post by bigleagueposter »

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

P = NP is trivially true on machines which compute everything instantly (using paradoxes).

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

#97

Post by babypistol »

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, there is an interesting section on that:

> If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power.

So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve.

That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?

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

#98

Post by zaarn »

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

Time and solution are usually abstract concepts here.

The time a turing machine takes to solve the problem can be considered local and in absense of general relativity, it doesn't matter much.

When you talk about time in NP/P, you usually talk about the O Notation (Big O and friends) which gives you the driving factor of the time needed to solve.

Ie, O(n) = 2 + 3x + 9x^2 + 9^x is n^x complexity because this part of the equation will grow much quicker than the others. In reality of course, it can take a while for the biggest part to overtake which is why searching an array linearly in CPU cache can be faster than a hashmap.

The solution in NP/P is usually reduced to either a predicate being proven true or the answer being boolean or can be reduced to either. (ie, solving a jig-saw puzzle can be reduced to "is this jig-saw puzzle solvable" which can be proven by presenting a solution)

The problem you present is not in the scope of NP/P. You're already involving multiple computers and generally here, people still assume general relativity doesn't exist. Plus NP still holds because one computer simply accessed a blackbox function (oracle) while the other solved it in NP.

Time-complexity isn't the only complexity either, you also have space-complexity.

SC tells you how much memory you need to solve a problem. Or rather, how quickly that memory need will grow. You can trade a lot of NP problems to P problems if you have "NP" space complexity.

SC complexity won't spit out a byte-accurate estimation of memory but it can tell you that O(n) = 100 + 100*x will grow linearly in size (O = x) and O(n) = 100 + x^2 will grow exponentially in memory usage (O = x^2).

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

#99

Post by yellowstuff »

ianai wrote: post #60
SolarNet wrote: post #20

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

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 less efficient.
Post reply on HN