Vinay Deolalikar, a researcher at HP Labs, has released a near-final draft of a paper called P ≠ NP. A professor at my school writes, "It will be some time before it is carefully checked by referees, but it is already rather clear to me that it is an interesting paper regardless of how well all the details check out. I am thinking that some of the faculty as well as some of the graduate students will be interested in this paper. It is an example of what Christine thought was missing when she set up this reading group." He's talking about the Algorithms Reading Group that Christine **lyceum_arabica** founded last year; he's also talking about the most important heretofore unsolved problem in theoretical computer science.
The paper is about a hundred pages long. All I've done so far is glance at the abstract and introduction, enough to see that the proof weaves together ideas from statistics, logic, and physics. For instance, here are some words and phrases that appear in the current draft: "conditional independence" (75 matches), "graphical model" (41 matches), "Markov property" (15 matches), "least fixed point" (21 matches), "monadic" (18 matches), "finite model theory" (14 matches), "Hamming distance" (8 matches), "thermodynamic limit" (5 matches), "clause density" (18 matches), "spin glasses" (2 matches).
In other words: dang.
There will be a lot of background material to cover before being able to understand the proof. I only went to the algorithms reading group once last year; it's not really my area, and besides, I was doing my time at Beer and Algorithms. I wasn't sure if I would go this year; I figured I probably wouldn't, since I'm supposed to be concentrating on PL research. But I *do* need one more theory course to round out my minor, and a discussion has sprung up on the group's mailing list of turning this fall's rendition of the group into a cumulative series of talks by students and faculty that will eventually lead to understanding this paper. Some of the talks can be given by students -- personally, I've got my eye on a "first-order logic extended with fixed points" talk. If the proof turns out to be correct, then by the end of the year, maybe we will sort of understand why P is not equal to NP. I don't know if I can turn down an opportunity like this. |