PL (complexity)

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).

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 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 >  1⁄2 (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 M and a number n, testing with |M|>n[note 1] is also PL complete. By contrast, testing whether matrix permanent is positive is PP complete.

PLPL=PL in the sense that for every f in PL, PL is unchanged if it is extended to allow ⁠x→f(A,x)⁠ as a subroutine, where A is the input string.

PL contains NL and BPL and is contained in NC2.

Approximating determinant in PL

edit edit source

Determinant of an integral matrix can be reduced to finding the difference between the number of accepting and rejecting paths on a polynomially sized directed acyclic graph with distinguished start, accept, and reject nodes. [1]

Comparing the number of accepting and rejecting paths can be done in PL as follows. Modify the graph to make all paths the same length and for each node to have at most two successors. Take a random path. For each node with just one successor, fail (output random answer) with probability 1⁄2. At the end, accept if we reached Accept node, reject if we reached Reject node, and fail otherwise. Each distinct path will be counted equally — while some paths are more likely to be taken, this is exactly compensated by reduced likelihood of continuing along that path.

Probabilistic logspace without a time limit

edit edit source

If time is unlimited, the machines can run in expected exponential time — for example, keep a counter and increment it with probability 1⁄2 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 ⁠1/2+1/s(n)⁠ of the time where ⁠s(n)⁠ 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 i, add a variable xi — probability of acceptance if current state is i. If there is no path from i to Accept, set xi=0, and otherwise express xi 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.[note 1] 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.

Notes

edit edit source
  1. ^ a b |A| denotes determinant of A Wikipedia revision 1254235063, retrieved 2026-11-18

References

edit edit source
  1. ^ Meena Mahajan; V Vinay (1997). "A Combinatorial Algorithm for the Determinant". In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM/SIAM. pp. 730–738. Wikipedia revision 1254235063, retrieved 2026-11-18
Complexity classesConsidered feasible Suspected infeasible Considered infeasible Other complexity classes Class hierarchies Families of classes List of complexity classes

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 2024-10-30 · not yet sealed in the ledger · verify the chain · version history

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