What is "pls"

abbr. please

PLS or Pls may refer to:

PLS is a computer file format for a multimedia playlist. It was originally developed for use with the museArc audio player software by codeArts, and was later used by SHOUTcast and Icecast for streaming media over the Internet. PLS is a more expressive playlist format than basic M3U, as it can store ( cache) information on the song title and length (this is supported in extended M3U only). With PLS version 2, playlists also include a PLS version declaration.

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 L has a set D of instances which are encoded using strings over a finite alphabet Σ. For each instance x there exists a finite solution set F(x). Each solution s ∈ F(x) has a non negative integer cost given by a function c(s, x) and a neighborhood N(s, x) ⊆ F(x). Additionally, the existence of the following three polynomial time algorithms is required:

• Algorithm A produces some solution A(x) ∈ F(x).
• Algorithm B determines the value of c(s, x).
• Algorithm C maps a solution s ∈ F(x) to an element sʹ ∈ N(s, x) such that c(sʹ, x) < c(s, x) if such an element exists. Otherwise C reports that no such element exists.

An instance D has the structure of an implicit graph, the vertices being the solutions with two solutions s, sʹ ∈ F(x) connected by a directed arc iff sʹ ∈ N(s, x). The most interesting computational problem is the following:

Given some instance x of a PLS problem L, find a local optimum of c(s, x), i.e. a solution s ∈ F(x) such that c(sʹ, x) ≥ c(s, x) for all sʹ ∈ N(s, x)

The problem can be solved using the following algorithm:

1. Use A to find an initial solution s
2. Use algorithm C to find a better solution sʹ ∈ N(s, x). If such a solution exists, replace s by sʹ, else return s

Unfortunately, it generally takes an exponential number of improvement steps to find a local optimum even if the problem L 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.