Typical-Case Complexity Results From a New Type of Phase Transition

The NP-Complete class of decision problems are simply stated tasks, for example in combinatorics, that may require enormous computing effort to solve. Heuristic methods 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 K-SAT, a widely studied NP-Complete problem. The nature of this phase transition can be understood in some detail, and the details suggest a mechanism for computational cost and directions for improving the efficiency of search heuristics. Randomness causes the transition to combine properties of the 1st order (discontinuous onset of ordering) and 2nd order (with power law scaling) transitions known inthe physics of pure solids. This type of transition should occur in other combinatoric problems defined on random structures, and possibly in granular media.