PLS (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computational complexity theory, Polynomial Local Search (PLS) 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 strings over a finite 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:

  • Algorithm produces some solution .
  • Algorithm determines the value of .
  • Algorithm maps a solution to an element such that if such an element exists. Otherwise reports that no such element exists.

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.