  Heuristic methods for solution of problems in the NP-Complete class of
decision problems often reach exact solutions, but fail badly at "phase
boundaries", across which the decision to be reached changes from almost always
having one value to almost having a different value. We report an analytic
solution and experimental investigations of the phase transition that occurs in
the limit of very large problems in K-SAT. The nature of its "random
first-order" phase transition, seen at values of K large enough to make the
computational cost of solving typical instances increase exponenitally with
problem size, suggest a mechanism for the cost increase. There has been
evidence for features like the "backbone" of frozen inputs which characterizes
the UNSAT phase in K-SAT in the study of models of disordered materials, but
this feature and this transition are uniquely accessible to analysis in K-SAT.
The random first order transition combines properties of the 1st order
(discontinuous onset of order) and 2nd order (with power law scaling, e.g. of
the width of the the critical region in a finite system) transitions known in
the physics of pure solids. Such transitions should occur in other combinatoric
problems in the large N limit. Finally, improved search heuristics may be
developed when a "backbone" is known to exist.
