Subject: NP-completeness and spin glasses
From: Cynbe ru Taren (cynbe)
Date: Fri Aug 13 1999 - 13:40:52 CDT
Here's a guy with some results in applying spin-glass notions to K-SAT
NP-complete problems. He's managed to apply the notion of a phase
transition to the structure of the K-SAT problem and to show that the
pragmatic difficulty of solving the problem relates to whether the
transition is continuous. Ghostview doesn't like his postscript :( so
I wasn't able to read the core Nature article, owell. I presume what
is happening is that the discontinuous transition disallows hillclimbing,
leaving only a combinatorial search of possibilities as a solution.
I think we'll see a general recognition in CS/AI over the next couple
of decades that one needs to deliberately design discontinuities out and
hillclimbing in when formulating problem paradigms. At least, I've been
thinking that for some time now. :)
http://www.cs.cornell.edu/home/selman/
This archive was generated by hypermail 2a24 : Thu Sep 16 1999 - 23:04:42 CDT