February 5, 2004 8:57 AM Subscribe

Can't Get No Satisfaction - This unassuming essay (it's in a state of half-decay with missing figures) is a fascinating (and accessible) overview of phase transitions in NP systems (it explains those terms). In other words: complex physical systems and difficult problems in computing are related. The seminal paper is here, and this is a list of other essays by the same author (links at foot of page).

posted by andrew cooke (4 comments total)

posted by andrew cooke (4 comments total)

it was the last part of the article i found interesting - the details of phase transitions. i agree that the np stuff is standard (it's there to make the article understandable to the general reader).

it's possible that the phase transition work is also standard undergrad compsci, of course - i'm self taught in computing so may just have been missing something obvious until now.

posted by andrew cooke at 10:23 AM on February 5, 2004

it's possible that the phase transition work is also standard undergrad compsci, of course - i'm self taught in computing so may just have been missing something obvious until now.

posted by andrew cooke at 10:23 AM on February 5, 2004

Judging by your website, I think you've easily surpassed most MSc's in compsci!

my complexity prof created the master method for recurrence relations, and was the daughter of the chap who solved the 4-colour theorem... so I might've had a bit more exposure to complexity than most :^)

I think the most interesting thing about NP problems is the tempting notion that quantum computing could put an end to them all.

If you like the phase-transitions stuff, read about Paul Erdos, a famous graph theoretician and quite possibly the most eccentric mathematician yet.

posted by krunk at 11:47 AM on February 5, 2004

my complexity prof created the master method for recurrence relations, and was the daughter of the chap who solved the 4-colour theorem... so I might've had a bit more exposure to complexity than most :^)

I think the most interesting thing about NP problems is the tempting notion that quantum computing could put an end to them all.

If you like the phase-transitions stuff, read about Paul Erdos, a famous graph theoretician and quite possibly the most eccentric mathematician yet.

posted by krunk at 11:47 AM on February 5, 2004

So I have just one question: should I take the blue pill or the red pill?

posted by ZenMasterThis at 3:06 PM on February 5, 2004

« Older Comprehensive collection of photo tutorials.... | How much is your personal info... Newer »

This thread has been archived and is closed to new comments

the brother of one of my undergrad profs spent several years biking around the world trying to prove P=NP. I'm not sure why he felt a bike was the best place to do so.

posted by krunk at 9:22 AM on February 5, 2004