PL (complexity)
id:
pl-complexity-306-1533402
title:
PL (complexity)
text:
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, testin
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/PL_(complexity)
date created:
date modified:
2021-01-29T22:31:17Z
main entity:
{"identifier":"Q22907784","url":"https://www.wikidata.org/entity/Q22907784"}
image:
fields total:
13
integrity:
13