PL (complexity)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

PL, or probabilistic L, is the class of languages recognizable by a polynomial time logarithmic space randomized machine with probability > (this is called unbounded error). Equivalently, as shown below, PL is the class of languages recognized by unbounded time unbounded error logspace randomized machine. An example of PL complete problem (under logspace reduction) is finding whether the determinant of a matrix (with integral coefficients) is positive. Given a matrix and a number , testing with |M|>n is also PL complete. By contrast, testing whether matrix permanent is positive is PP complete. PL PL =PL in the sense that for every f in PL, PL is unchanged if it is extended to allow as a subroutine, where A is the input string. PL contains NL and BPL and is contained in NC 2 .

PL, or probabilistic L, is the class of languages recognizable by a polynomial time logarithmic space randomized machine with probability >  (this is called unbounded error). Equivalently, as shown below, PL is the class of languages recognized by unbounded time unbounded error logspace randomized machine. An example of PL complete problem (under logspace reduction) is finding whether the determinant of a matrix (with integral coefficients) is positive. Given a matrix and a number , testing with |M|>n is also PL complete. By contrast, testing whether matrix permanent is positive is PP complete. PL PL =PL in the sense that for every f in PL, PL is unchanged if it is extended to allow as a subroutine, where A is the input string. PL contains NL and BPL and is contained in NC 2 . If time is unlimited, the machines can run in expected exponential time — for example, keep a counter and increment it with probability and zero it otherwise; halt when the counter overflows. If zero error (alternatively, one-sided error) is allowed, the class equals NL — the machine can simulate NL by trying random paths for an exponential amount of time and using NL=coNL. If bounded error is allowed, a complete promise or approximation problem is estimating stationary distribution for an ergodic Markov chain. The complexity class is not known to equal PL, and an attempt to simulate PL through blackbox probability amplification fails: Despite unbounded time, bounded error logspace machines cannot distinguish a random coin from one that lands head of the time where grows superpolynomially. For unbounded error logspace machines, unbounded time can be reduced to polynomial time as follows. Computing acceptance probability can be reduced to solving a linear system. For each state , add a variable — probability of acceptance if current state is i. If there is no path from i to Accept, set , and otherwise express in terms of states immediately reachable from state i. The system can be solved using determinants, and testing whether |A|>2|B| is in PL. One complication is that the coefficients are in NL (using NL=coNL). We address it by guessing a 'proof' for each coefficient value, failing if the guess does not work, and ensuring that all paths make the same number of guesses for each coefficient.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1254235063 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001254235063 · captured 1730247424.0 · version history

Cite this page as: encyclopegia.org, “PL (complexity)”, snapshot enwiki-001254235063. https://encyclopegia.org/a/pl-complexity

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.