News for hackers. Stuff that matters.
Re:Markets are efficient if and only if P = NP by jplewicke on Tuesday February 23, 2010 @11:00AM (#1145623)
When I first saw the headline, I assumed it was going to be about the CDO packing problem discussed at http://rjlipton.wordpress.com/2009/10/22/helping-wall-street... . The basic idea is that if you're buying a Collateralized Debt Obligation, you can't tell whether the people structuring the deal have intentionally given you an unfair share of bad loans, even when you know a lot about each of the loans in particular.

There's also a fairly trivial argument for the incomputability of the EMH: for each Turing machine, issue bonds that compound interest in perpetuity and pay it off if the Turing machine halts. Since the value of the bond is positive if the Turing machine halts and zero if it doesn't, in an efficient market investors will price the bonds in a way that solves the halting problem.

Re:Markets are efficient if and only if P = NP by aprime on Tuesday February 23, 2010 @11:14AM (#1145649)
Doesn't this only prove that there cannot be an efficient market for these special "Turing machine" bonds?
Re:Markets are efficient if and only if P = NP by jplewicke on Tuesday February 23, 2010 @12:35PM (#1145847)
That's definitely true. It's only a counterproof to some extremely strong versions of the EMH that assume that you can buy any possible asset or derivative. http://en.wikipedia.org/wiki/Complete_market