Posts Tagged ‘P=NP’

I hope that P does not equal NP

Monday, August 9th, 2010

And, further, I hope that this Vinay Deolalikar guy proved it. I don’t normally will mathematics to behave a certain way, but in this case I make an exception for a few reasons. (For a quick primer on the P=NP problem, check out Wikipedia).

First, I like hearing about epic math problems that have been solved. And learning about how they were solved, and who solved them, and who came up with those problems in the first place, and everything that was going on at the time that led up to the discoveries. I find this stuff fascinating. It’s like Edmund Hilary scaling Mount Everest, except with maths. In college my friends and I watched a documentary on Fermat’s Last Theorem and Andrew Wiles’ pwning the hell out of it. We had a glorious time. Oh, I also read a book about Godel’s incompleteness theorems. That was similarly awesome.

Second, there is a paper which proves markets are efficient iff P=NP (“iff” is pronounced “if and only if”). Now, I’m pretty sure markets aren’t efficient. It’s my opinion that a belief in the efficient markets hypothesis is correlated with being more of a jerk. Fightin’ words, I know, but economists in general (and market fundamentalists in particular) could use a little more humility. But I digress. I’m not sure how much play the “P=NP <=> efficient markets” paper got, or if anyone proved it; and I remember Tyler Cowen didn’t think much of the claim, but I hope it’s correct. These two papers, then, would prove mathematically that markets aren’t efficient. I would feel vindicated, and people like Eugene Fama and his followers would be provably incorrect.

Third, I am a big fan of the general approach Vinay Deolalikar used in his proof.  I can’t find a good summary online, so here goes: basically he drew from a whole bunch of fields, saw the conceptual similarities among a bunch of otherwise very narrow branches of maths, and stitched together a diverse, “multidisciplinary” proof (all while filling in the nitty gritty details, of course). I will always be a fan of the general over the specific; in general I think a broad view is more valuable than a narrow one. If a problem of epic proportions, like P=NP, can be solved by taking a step back and tying what we already know together, rather than going deeper and deeper into sub-sub-subfields that have probably been mined of intellectual value long ago, it will make me very happy.


Creative Commons Attribution 3.0 Unported
This work is licensed under a Creative Commons Attribution 3.0 Unported.