Computer Science – Artificial Intelligence
Scientific paper
2011-06-22
Journal Of Artificial Intelligence Research, Volume 17, pages 309-332, 2002
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.1081
In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.
Culberson Joseph
Gao Yanfang
No associations
LandOfFree
An Analysis of Phase Transition in NK Landscapes 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 An Analysis of Phase Transition in NK Landscapes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Analysis of Phase Transition in NK Landscapes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-469014