is another vertex cover only differing by one node. For boolean satisfiability, the neighbors of a boolean assignment are those that have a single variable in an opposite state. The same problem may have multiple distinct neighborhoods defined on it; local optimization with neighborhoods that involve changing up to k components of the solution is often referred to as k-opt. Typically, every candidate solution has more than one neighbor solution; the choice of which one to select is taken using only information about the solutions in the neighborhood of the current assignment, hence the name local search. When the choice of the neighbor solution is done by taking the one locally maximizing the criterion, i.e.: a greedy search, the metaheuristic takes the name hill climbing. When no improving neighbors are present, local search is stuck at a locally optimal point. This local-optima problem can be cured by using restarts (repeated local search with different initial conditions), randomization, or more complex schemes based on iterations, like iterated local search, on memory, like reactive search optimization, on memory-less stochastic modifications, like simulated annealing. Local search does not provide a guarantee that any given solution is optimal. The search can terminate after a given time bound, or when the best solution found thus far has not improved in a given number of steps. Local search is an anytime algorithm: it can return a valid solution even if it's interrupted at any time after finding the first valid solution. Local search is typically an approximation or incomplete algorithm, because the search may stop even if the current best solution found is not optimal. This can happen even if termination happens because the current best solution could not be improved, as the optimal solution can lie far from the neighborhood of the solutions crossed by the algorithm. Schuurman & Southey propose three measures of effectiveness for local search (depth, mobility, and coverage): depth: the cost of the current (best) solution; mobility: the ability to rapidly move to different areas of the search space (whilst keeping the cost low); coverage: how systematically the search covers the search space, the maximum distance between any unexplored assignment and all visited assignments. They hypothesize that local search algorithms work well, not because they have some understanding of the search space, but because they quickly move to promising regions, and explore the search space at low depths as quickly, broadly,