PL (complexity)

PL is 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 bounded-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 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 x→f(A,x) as a subroutine, where A is the input string.

PL contains NL and BPL and is contained in NC₂.

Approximating Determinant in PL

Determinant of an integral matrix can be reduced to finding the difference between the number of accepting and rejecting paths on a polynomially sized acyclic graph.

Comparing the number of accepting and rejecting paths can be done in PL as follows. Normalize the paths to have the same length. Take a random path. At each step continue with probability exactly k*d, where k is some constant independent of path (and current node) and d is the number of possibilities at that step; otherwise output a random answer. One can select k for this to be possible in randomized logspace. At the end, accept iff the path is an accepting one. 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

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, the class equals PL. To simulate PL, repeatedly simulate a PL machine until we have n^k consecutive acceptances or rejections for a large enough k. For the reverse inclusion, consider an unbounded time machine T and its configuration transition probability matrix M. For each pair of states, add a tiny transition probability between them (ε*2^-N works to estimate acceptance probability of T with 2^-O(1/ε) error where N is the number of states), and let M' be the modified matrix. As time approaches infinity, the modified machine will converge to a stationary probability distribution v with M'v=v and M' having no other eigenvectors with eigenvalue 1. We can then use determinants to compute v, and thus approximate the acceptance probability of T.