Can't Get No Satisfaction

February 5, 2004 8:57 AM

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)

that article is pretty standard undergrad CS stuff; basically all NP-complete problems can be reduced to SAT. if you find a polynomial algorithm for any one of them, you've found it for all of them. (and therefore proved that P=NP, and put a lot of people out of work)

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

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

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

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