Iterative Improvement Algorithms and Hill-Climbing

Since the evaluation used looks only at the current state, hill-climbing does not suffer from computational space issues. The source of its computational complexity arises from the time required to explore the problem space.

Random-restart hill-climbing can arrive at optimal solutions within polynomial time for most problem spaces. However, for some NP-complete problems, the numbers of local maxima can be the cause of exponential computational time. To address these problems some researchers have looked at using probability theory and local sampling to direct the restarting of hill-climbing algorithms.