?

Log in

No account? Create an account
P ≠ NP - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

P ≠ NP [Aug. 9th, 2010|10:54 pm]
Lindsey Kuper

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.

LinkReply

Comments:
[User Picture]From: keystricken
2010-08-10 05:20 am (UTC)
I love propositional logic so much, it's almost indecent. I can't wait to look at this paper, and I'm so envious that you will have a reading group. Do it do it dooooooo iiiiit.
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-08-10 11:38 am (UTC)
At the risk of being a complete tool, I think you actually love logic so much it's almost indecent. Propositional logic isn't the flavor we're talking about here.

In any case, the part of this that I didn't mention but that I think you'll appreciate is that I'm not really supposed to be taking classes at all this fall, and probably the most I can reasonably get away with is one, which means that if I do this, I might have to forgo taking Hofstadter's class again.
(Reply) (Parent) (Thread)
[User Picture]From: keystricken
2010-08-10 12:06 pm (UTC)
AUGH
WHAT
NO
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-08-11 12:27 am (UTC)
Don't worry, there'll be time later -- I'm serving a 5-to-life sentence.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-09-11 08:09 pm (UTC)
I decided to take the Hofstadter course anyway and skip out on the P != NP stuff. I'll have more detailed things to say about it at some point, but I just wanted to let you know that you can stop going AUGH.
(Reply) (Parent) (Thread)
[User Picture]From: keystricken
2010-09-12 07:20 pm (UTC)
AUGH Hooray!
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: lindseykuper
2010-08-10 01:41 pm (UTC)
If I could properly pronounce the word "chutzpah", I'd be saying that Scott Aaronson has a lot of it.
(Reply) (Parent) (Thread)
[User Picture]From: oniugnip
2010-08-11 01:22 am (UTC)
(can you say "ch"? It's a good sound to have handy.)
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2010-08-12 02:30 am (UTC)
Not as well as you can!
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: lindseykuper
2010-08-10 11:46 am (UTC)
The comparison between the limitations of first-order logic and the nature of NP doesn't seem far-fetched to me at all. But the parts about statistical physics might as well be magic to me.

Ooh, I left "Hamming distance" out of my litany of phrases. And "thermodynamic limit".
(Reply) (Parent) (Thread)
(Deleted comment)
(Deleted comment)
(Deleted comment)
[User Picture]From: jes5199
2010-08-11 06:48 am (UTC)
soapbox- this is a 21st century proof.
Like the proof of Fermat's Last Theorem, it fails to provide the feeling of elegance and enlightenment that we generally expect from a proof of a fundamental conjecture. It successfully banishes the mystery from the conjecture without replacing it with understanding. And the world goes on being slightly more certain of something that we were pretty sure of all along.


I've never even heard of statistical physics before yesterday.
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-08-11 01:02 pm (UTC)
Well, of course it isn't going to be anywhere near as elegant as this. Also, my Scheme compiler is nowhere near as elegant as an abacus. Or, to pick an example from a wildly different field, 21st century feminism is a hell of a lot harder to understand than first-wave feminism. That doesn't mean I'd want to go back.

As knowledge in a field progresses, we run out of straightforward things to think about, and we have to start thinking about less straightforward things. I think that this proof is elegant in a different way, in that it brings together ideas from very different areas. Considering how here in the 21st century, almost everyone with a Ph.D. is an extreme specialist, it's remarkable when someone has a broad vision that cuts across fields. I think it's awesome that the proof of P != NP, if that's what it turns out to be, incorporates stuff from a field that I hadn't heard of. Maybe this will lead to more cooperation and communication among the fields.

And the other kind of elegance is there, too, but it's harder to see because more background material is necessary to understand it. If I don't find something at the core of this proof that I think is elegant, then I'll buy you a beer.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2010-08-11 05:09 pm (UTC)
When you can describe to me the elegant kernel of this proof, I'll buy you a beer.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2010-08-18 08:16 am (UTC)
heard a rumor that the paper sprang a leak
(Reply) (Thread)
[User Picture]From: lindseykuper
2010-08-18 11:58 pm (UTC)
Yeah, a lot of questions have been raised about it. Dick Lipton's amazing blog is keeping track.
(Reply) (Parent) (Thread)