PLS (complexity)


In computational complexity theory, Polynomial Local Search is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time 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.

Description

When searching for a local optimum, there are two interesting issues to deal with: First how to find a local optimum, and second how long it takes to find a local optimum. For many local search algorithms, it is not known, whether they can find a local optimum in polynomial time or not. So to answer the question of how long it takes to find a local optimum, Johnson, Papadimitriou and Yannakakis introduced the complexity class PLS in their paper "How easy is local search". It contains local search problems for which the local optimality can be verified in polynomial time.
A local search problem is in PLS, if the following properties are satisfied:
With these properties, it is possible to find for each solution the best neighboring solution or if there is no such better neighboring solution, state that is a local optimum.

Example

Consider the following instance of the Max-2Sat Problem:. The aim is to find an assignment, that maximizes the sum of the satisfied clauses.
A solution for that instance is a bit string that assigns every the value 0 or 1. In this case, a solution consists of 3 bits, for example, which stands for the assignment of to with the value 0. The set of solutions is the set of all possible assignments of, and.
The cost of each solution is the number of satisfied clauses, so because the second and third clause are satisfied.
The Flip-neighbor of a solution is reached by flipping one bit of the bit string, so the neighbors of are with the following costs:
There are no neighbors with better costs than, if we are looking for a solution with maximum cost. Even though is not a global optimum, is a local optimum, because none of its neighbors has better costs.
Intuitively it can be argued that this problem lies in PLS, because:
A local search problem has a set of instances which are encoded using strings over a finite alphabet. For each instance there exists a finite solution set. Let be the relation that models. The relation is in PLS if:
An instance has the structure of an implicit graph, the vertices being the solutions with two solutions connected by a directed arc iff.
A local optimum is a solution, that has no neighbor with better costs. In the implicit graph, a local optimum is a sink. A neighborhood where every local optimum is a global optimum, which is a solution with the best possible cost, is called an exact neighborhood.

Example neighborhood structures

Example neighborhood structures for problems with boolean variables as solution:
Example neighborhood structures for problems on graphs:
Consider the following computational problem:
Given some instance of a PLS problem, find a locally optimal solution such that for all .
Every local search problem can be solved using the following iterative improvement algorithm:
  1. Use to find an initial solution
  2. Use algorithm to find a better solution. If such a solution exists, replace by and repeat step 2, 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. It is not necessary always to use the standard algorithm, there may be a different, faster algorithm for a certain problem. For example a local search algorithm used for Linear programming is the Simplex algorithm.
The run time of the standard algorithm is pseudo-polynomial in the number of different costs of a solution.
The space the standard algorithm needs is only polynomial. It only needs to save the current solution, which is polynomial bounded by definition.

Reductions

A Reduction of one problem to another may be used to show that the second problem is at least as difficult as the first. In particular, a PLS-reduction is used to prove that a local search problem that lies in PLS is also PLS-complete, by reducing a PLS-complete Problem to the one that shall be proven to be PLS-complete.

PLS-reduction

A local search problem is PLS-reducable to a local search problem if there are two polynomial time functions and such that:
It is sufficient to only map the local optima of to the local optima of, and to map all other solutions for example to the standard solution returned by.
PLS-reductions are transitive.

Tight PLS-reduction

Definition [|Transition graph]

The transition graph of an instance of a problem is a directed graph. The nodes represent all elements of the finite set of solutions and the edges point from one solution to the neighbor with strictly better cost. Therefore it is an acyclic graph. A sink, which is a node with no outgoing edges, is a local optimum.
The height of a vertex is the length of the shortest path from to the nearest sink.
The height of the transition graph is the largest of the heights of all vertices, so it is the height of the largest shortest possible path from a node to its nearest sink.

Definition Tight PLS-reduction

A PLS-reduction from a local search problem to a local search problem is a
tight PLS-reduction if for any instance of, a subset of solutions
of instance of can be chosen, so that the following properties are satisfied:
PLS lies between the functional versions of P and NP: FP ⊆ PLS ⊆ FNP.
PLS also is a subclass of TFNP, 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 to another.
It is also proven that if a PLS problem is NP-hard, then NP = co-NP.

PLS-completeness

Definition

A local search problem is PLS-complete, if
The optimization version of the circuit problem under the Flip neighborhood structure has been shown to be a first PLS-complete problem.

List of PLS-complete Problems

This is an incompete list of some known problems that are PLS-complete.
Notation: Problem / Neighborhood structure