Locating phase transitions in computationally hard problems

Details Locating phase transitions in computationally hard problems Locating phase transitions in computationally hard problems

2010-05-11

arxiv.org/abs/1005.1941v1

Physics

Condensed Matter

Statistical Mechanics

To appear in Pramana: journal of physics (2010) (in press)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Locating phase transitions in computationally hard problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Locating phase transitions in computationally hard problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locating phase transitions in computationally hard problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498426