PLS (complexity)

From formulasearchengine
Jump to navigation Jump to search

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

A PLS problem has a set of instances which are encoded using an alphabet . For each instance there exists a finite solution set . Each solution has a non negative integer cost given by a function and a neighborhood . Additionally, the existence of the following three polynomial time algorithms is required:

An instance has the structure of an implicit graph, the vertices being the solutions with two solutions connected by a directed arc iff . The most interesting computational problem is the following:

Given some instance of a PLS problem , find a local optimum of , i.e. a solution such that for all

The problem can be solved using the following algorithm:

  1. Use to find an initial solution
  2. Use algorithm to find a better solution . If such a solution exists, replace by , else return

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem 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 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.


  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.