193.61.28.57: reverting vandalism

2012-04-04T20:28:34Z

reverting vandalism

New page

In [[computational complexity theory]], '''PLS''', which stands for Polynomial Local Search, is a [[complexity class]] that models the difficulty of finding a [[local optimum|locally optimal]] solution to an [[optimization problem]].

A PLS problem <math>L</math> has a set <math>D_L</math> of instances which are encoded using an [[Alphabet (computer science)|alphabet]] <math>\Sigma^*</math>. For each instance <math>x</math> there exists a finite solution set <math>F_L(x)</math>. Each solution <math>s \in F_L(x)</math> has a non negative integer cost given by a function <math>c_L(s, x)</math> and a neighborhood <math>N(s, x) \subseteq F_L(x)</math>. Additionally, the existence of the following three [[Polynomial_time_algorithm#Polynomial_time|polynomial time]] algorithms is required:

* Algorithm <math>A_L</math> produces some solution <math>A_L(x) \in F_L(x)</math>.
* Algorithm <math>B_L</math> determines the value of <math>c_L(s, x)</math>.
* Algorithm <math>C_L</math> maps a solution <math>s \in F_L(x)</math> to an element <math>s' \in N(s, x)</math> such that <math>c_L(s', x) < c_L(s, x)</math> if such an element exists. Otherwise <math>C_L</math> reports that no such element exists.

An instance <math>D_L</math> has the structure of an [[implicit graph]], the vertices being the solutions with two solutions <math>s, s' \in F_L(x)</math> connected by a directed arc iff <math>s' \in N(s, x)</math>. The most interesting computational problem is the following:

''Given some instance <math>x</math> of a PLS problem <math>L</math>, find a local optimum of <math>c_L(s, x)</math>, i.e. a solution <math>s \in F_L(x)</math> such that <math>c_L(s', x) \geq c_L(s, x)</math> for all <math>s' \in N(s, x)</math>''

The problem can be solved using the following algorithm:

# Use <math>A_L</math> to find an initial solution <math>s</math>
# Use algorithm <math>C_L</math> to find a better solution <math>s' \in N(s, x)</math>. If such a solution exists, replace <math>s</math> by <math>s'</math>, else return <math>s</math>

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem <math>L</math> can be solved exactly in polynomial time.

Examples of PLS-complete problems include local-optimum relatives of the [[travelling salesman problem]], [[maximum cut]] and [[satisfiability]], as well as finding a pure [[Nash equilibrium]] in a [[congestion game]].

PLS is a subclass of [[TFNP]], a complexity class closely related to [[NP (complexity)|NP]] that describes computational problems in which a solution is guaranteed to exist and can be recognized in polynomial time. For a problem in PLS, a solution is guaranteed to exist because the minimum-cost vertex of the entire graph is a valid solution, and the validity of a solution can be checked by computing its neighbors and comparing the costs of each one.

== References ==
* {{Citation | last1=Yannakakis | first1=Mihalis | author1-link=Mihalis Yannakakis | title=Equilibria, fixed points, and complexity classes | publisher=[[Elsevier]] | year=2009 | journal=Computer Science Review | volume=3 | issue=2 | pages=71–85}}.

{{comp-sci-theory-stub}}
[[Category:Complexity classes]]

Compactness measure of a shape - Revision history

193.61.28.57: reverting vandalism