PLS (complexity)

PLS (complexity)

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-optimumrelatives of TSP, MAXCUT and SAT.

References

* http://www.cs.berkeley.edu/~alexf/papers/fpt04-stoc-slides.pdf


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • PLS — or Pls may mean:* Papillon Lefevre syndrome a disease affecting the teeth and skin * Liberal Party of Switzerland (Partito Liberale Svizzero) * Polish Volleyball League ( Polska Liga Siatkówki ) * Partial least squares (statistics) * Palletized… …   Wikipedia

  • Complete (complexity) — In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the hardest or most expressive problems in the complexity class. If a problem has the property that it allows you… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Wikipedia:Featured article candidates — Here, we determine which articles are to be featured articles (FAs). FAs exemplify Wikipedia s very best work and satisfy the FA criteria. All editors are welcome to review nominations; please see the review FAQ. Before nominating an article,… …   Wikipedia

  • Gulf Cartel — Founded 1970s In Matamoros, Tamaulipas, Mexico Founded by Juan Nepomuceno Guerra, Juan García Abrego Years active 1970s−present Territory Mexico: Ta …   Wikipedia

  • Configurable Network Computing — or CNC is JD Edwards s (JDE) client–server proprietary architecture and methodology that implements its highly scalable enterprise wide business solutions software that can run on a wide variety of hardware, operating systems (OS) and hardware… …   Wikipedia

  • 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 binary relation P( x , y ) is in TFNP if and only if there is …   Wikipedia

  • Plant — For other uses, see Plant (disambiguation). Plants Temporal range: Early Cambrian to recent, but see text, 520–0 Ma …   Wikipedia

  • Translation memory — A translation memory, or TM, is a type of database that stores segments that have been previously translated. A translation memory system stores the words, phrases and paragraphs that have already been translated and aid human translators. The… …   Wikipedia

  • Cascading Style Sheets — CSS redirects here. For other uses, see CSS (disambiguation). For the use of CSS on Wikipedia, see Help:Cascading style sheets. Cascading Style Sheets Filename extension .css Internet media type text/css Developed by World Wide Web Consortium …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”