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).
An example of PL complete problem (under logspace reduction) is finding whether the determinant of a matrix (with integral coefficients) is positive.
By contrast, testing whether matrix permanent is positive is PP complete.
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.
Modify the graph to make all paths the same length and for each node to have at most two successors.
For each node with just one successor, fail (output random answer) with probability 1⁄2.
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
Computing acceptance probability can be reduced to solving a linear system.