# Can't Get No Satisfaction

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).

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

*In other words: complex physical systems and difficult problems in computing are related.*

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 Luminous Photo Help | what are your bits worth? 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