News for hackers. Stuff that matters.
Re:Markets are efficient if and only if P = NP by yummyfajitas on Tuesday February 23, 2010 @12:24AM (#1144765)
Dupe. This paper is new, but the result is not.

The paper Betting on Permutations by Pennock, Chen, Fortnow and Nikolova already proves this.

Consider a race between n runners. Now consider a prediction market accepting bets of the form "X will finish before Y". They prove that the market maker/auctioneer problem is NP hard. Conversely, if markets are efficient, then they solve the market maker/auctioneer problem.

Re:Markets are efficient if and only if P = NP by Spark23 on Tuesday February 23, 2010 @05:00AM (#1145093)
But having an efficient market doesn't imply that an algorithm \in P exists for that problem ?? Efficient markets just imply decidability of the problem.