In the last two days a firestorm has erupted over a claim by HP Labs computer scientist, Vinay Deolalikar, http://wwww.hpl.hp.com/personal/Vinay_Deolalikar/Papers that he has proven one of the six remaining Clay problems for which a million dollar prize is offered. In particular, he claims to have proven that polynomial time algorithms (P) cannot in general solve exponential time problems (NP), or are not equivalent in power to them. It has long been suspected that this is the case, but has not been proven so far. This has implications for computational complexity theory and computable and computational economics.
The paper is over 100 pages long and involves ideas drawn from model theory in logic as well as statistical physics, an approach not used for anything previously, and so far in the enormous debate that has erupted, there is not yet a definite answer if Deolalikar is right or not, although some minor errors have definitely been found. An aggregator site for this debate is at http://michaelnielson.org/polymath1/indep.php?title=Deolalikar%27s_P!%3DNP_paper. This site provides links to others where more detailed debates have been occurring, with the ones starting with http://rjlipton.wordpress.com being especially insightful and providing most of the mathematical meat picked up on the aggregator site.
The latest on this from the Lipton postings seems to be leaning to that Deolalikar does not have it on several grounds, but that his approach will stimulate a lot of research bringing together ideas and fields and approaches not brought together previously, with some of this having implications for computational economics, econophysics, and some other areas of economics, as well as many other fields.
ReplyDeleteGame back on. Deolalikar has put up a new version that answers some of the critics.
ReplyDeletei note that harvey friedman (FOM) says this is a sociological issue; there was another interesting proof of p/np (i forget which) from someone in the ussr with what looked like good credentials last month posted, which got no press. this person is from hp so they, like ibm or xerox, would get a nod. not no foreigner.
ReplyDeletei read the reviews (lipton, etc.) and then found a summary by some cal tech grad student. didnt even look at 121 pages. it actually sounds laughable enough to read. they apparently try to find a 'phase transition' in the k-sat problem (well studied by sherrignton and kirkpatrick) which somehow will seperate p from np. that dog wont hunt. where's that haystack? can't even find a vein. (speakin as an amateur).
i'm actually sympathetic with Bollobos (of graph theory) in the poll Friedman cites on his web site of expert opinion on p=np (or donald knuth) (though one may need a few re-definitions). p=np.
a logical fallacy.
the main thing interesting actually (assuming the paper is wrong) is what role model theory played in it. probably just filler (rigorous obfuscationism, inc.) but it is relevant.