  We discuss how phase-transitions may be detected in computationally hard
problems in the context of Anytime Algorithms. Treating the computational time,
value and utility functions involved in the search results in analogy with
quantities in statistical physics, we indicate how the onset of a
computationally hard regime can be detected and the transit to higher quality
solutions be quantified by an appropriate response function. The existence of a
dynamical critical exponent is shown, enabling one to predict the onset of
critical slowing down, rather than finding it after the event, in the specific
case of a Travelling Salesman Problem. This can be used as a means of improving
efficiency and speed in searches, and avoiding needless computations.
