PLS (complexity)

From Wikipedia, the free encyclopedia

You have new messages (last change).

PLS is a syntactic subclass of TFNP. A instance of PLS can be given in terms of polynomial algorithms that determine an exponentially sized graph. Given an input x and a vertex in the graph, the polynomial algorithms can compute the neighbors of the vertex in the graph and the cost of the vertex in the graph.

An algorithm for a PLS problem, given an input x, will find a vertex in the graph such that no neighbor has better cost. This class is a subclass of TFNP, because every dag has a sink.

Examples of PLS-complete problems include local-optimum relatives of TSP, MAXCUT and SAT.

[edit] References


 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../p/l/s/PLS_%28complexity%29_4e6a.html"