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

71–80 of 201 posts

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

#71

Post by yoklov »

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 your `isValidSolution(input, solution)` function needs to take `O(n)`, `O(n^2)`, `O(n^3)`, (etc.) time or better.)

Essentially, a NP problem is a problem where you have to brute force the solution, but it's easy to know when you've found the correct solution.

If P = NP that means that there are no problems where this is true -- it would mean that any problem where it's easy to know if you've found the solution also has an algorithm for finding it more efficiently than brute force.

Your neural network example doesn't apply because training a neural network doesn't require brute forcing the solution space of the neural network weights. That would be crazy. So it's a problem in P.

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

#72

Post by [deleted] »

SolarNet wrote: post #68
lajhsdfkl wrote: post #63

Earlier quoted context omitted.

> then it implies that there is nothing special about markets How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource. What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods…

> It implies simply that markets are not efficient. No it implies that efficient market states are an NP complete problem. And that we are likely approximating the optimization of efficiency (of the allocation of resources) using markets. Different approximation algorithms have different properties. Might markets be the best in every possible way, sure, but it's very unlikely given what we know about approximation al…

[deleted]

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

#73

Post by csomar »

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…

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

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

#74

Post by jonathanstrange »

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.

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

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

#75

Post by mortdeus »

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…

What I am trying to understand is why this is considered a solvable problem, when essentially you need to devise a method to find a better solution to the problem in order to prove that there isn't a solution.

Aren't all proofs flawed in this way?

Like for example, 2 = fish. Prove that there isn't an undiscovered mathematical axiom that makes this not nonsense?

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

#77

Post by zaarn »

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…

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 interpretation) use the instruction that gives the result fastest or explore all instruction branches at once.

Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct.

Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem).

Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine.

Atleast this above is what I learned in CS course 2nd semester.

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

#78

Post by lajhsdfkl »

SolarNet wrote: post #68
lajhsdfkl wrote: post #63

Earlier quoted context omitted.

> then it implies that there is nothing special about markets How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource. What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods…

> It implies simply that markets are not efficient. No it implies that efficient market states are an NP complete problem. And that we are likely approximating the optimization of efficiency (of the allocation of resources) using markets. Different approximation algorithms have different properties. Might markets be the best in every possible way, sure, but it's very unlikely given what we know about approximation al…

> If those equivalent resources are thousands (or millions) of government panels then we should be able to mathematically prove equivalency.

There is a method of solving an NP complete problem with thousands (or millions) of government panels?

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

#79

Post by zeth___ »

csomar wrote: post #73
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…

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

Post reply on HN