Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
PLS (complexity)
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, Polynomial Local Search (PLS) is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> that models the difficulty of finding a <a href="/facts/Local_optimum/f40GlzAw">locally optimal</a> solution to an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a>. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in <a href="/facts/Time_complexity/77T62gmf">polynomial time</a> and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time. Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. </p>