PLS (complexity)
Encyclopedia
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
.
An instance of PLS has the structure of an implicit graph
, defined by a polynomial-time algorithm for computing the neighbors of each vertex
in the graph, together with another polynomial-time algorithm for computing a cost for each vertex. A valid solution to the instance is a vertex v in the graph for which no neighbor of v has smaller cost. If there is more than one such vertex, they are all valid.
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, PLS, which stands for Polynomial Local Search, is a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
that models the difficulty of finding a locally optimal
Local optimum
Local optimum is a term in applied mathematics and computer science.A local optimum of a combinatorial optimization problem is a solution that is optimal within a neighboring set of solutions...
solution to an optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
.
An instance of PLS has the structure of an implicit graph
Implicit graph
In the study of graph algorithms, an implicit graph representation is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some more concise input.-Neighborhood representations:The notion of an implicit graph...
, defined by a polynomial-time algorithm for computing the neighbors of each vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in the graph, together with another polynomial-time algorithm for computing a cost for each vertex. A valid solution to the instance is a vertex v in the graph for which no neighbor of v has smaller cost. If there is more than one such vertex, they are all valid.
Examples of PLS-complete problems include local-optimum relatives of the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
, maximum cut
Maximum cut
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.The problem can be stated simply as follows...
and satisfiability, as well as finding a pure Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
in a congestion game
Congestion game
Congestion games are a class of games in game theory first proposed by Rosenthal in 1973. In a Congestion game we define players and resources, where the payoff of each player depends on the resources it chooses and the number of players choosing the same resource. Congestion games are a special...
.
PLS is a subclass of TFNP
TFNP
In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."...
, a complexity class closely related to NP
NP
-Locations:* NP postcode area, Newport, United Kingdom* NP, country code for Nepal ** .np, the country code top level domain for Nepal* NP, anabbreviation for Ngee Ann Polytechnic, Singapore...
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.