Non-deterministic polynomial time (commonly termed 'NP-complete') problems
are relevant to many computational tasks of practical interest-such as the
'travelling salesman problem'-but are difficult to solve: the computing tim
e grows exponentially with problem size in the worst case. It has recently
been shown that these problems exhibit 'phase boundaries', across which dra
matic changes occur in the computational difficulty and solution character-
the problems become easier to solve away from the boundary. Here we report
an analytic solution and experimental investigation of the phase transition
in K-satisfiability, an archetypal NP-complete problem. Depending on the i
nput parameters, the computing time may grow exponentially or polynomially
with problem size; in the former case, we observe a discontinuous transitio
n, whereas in the latter case a continuous (second-order) transition is fou
nd. The nature of these transitions may explain the differing computational
costs, and suggests directions for improving the efficiency of search algo
rithms. Similar types of transition should occur in other combinatorial pro
blems and In glassy or granular materials, thereby strengthening the link b
etween computational models and properties of physical systems.