About: PL (complexity)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : dbo:Language, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FPL_%28complexity%29&invfp=IFP_OFF&sas=SAME_AS_OFF

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. PLPL=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 NC2.

AttributesValues
rdf:type
rdfs:label
  • PL (complexity) (en)
  • PL (complexidade) (pt)
rdfs:comment
  • 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. PLPL=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 NC2. (en)
  • PL, ou L probabilístico, é a classe de linguagens reconhecíveis por uma máquina randômica de espaço logarítmico de tempo polinomial com probabilidade > 1/2 (chamado de erro ilimitado). De forma equivalente, como mostrado abaixo, PL é a classe de linguagens reconhecidas por máquinas randômizadas de tempo ilimitado e de espaço log com erro ilimitado. PLPL=PL no sentido de que para cada f em PL, PL é inalterada se for alargada para x→f(A,x) como uma subrotina, onde A é a string de entrada. PL contém NL e BPL , e está contida em NC2. (pt)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • 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 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 as a subroutine, where A is the input string. PL contains NL and BPL and is contained in NC2. (en)
  • PL, ou L probabilístico, é a classe de linguagens reconhecíveis por uma máquina randômica de espaço logarítmico de tempo polinomial com probabilidade > 1/2 (chamado de erro ilimitado). De forma equivalente, como mostrado abaixo, PL é a classe de linguagens reconhecidas por máquinas randômizadas de tempo ilimitado e de espaço log com erro ilimitado. Um exemplo de problema PL completo (sob redução logspace) é encontrar se o determinante de uma matriz (com coeficientes inteiros) é positivo. Dados uma matriz M e um número n, testar se |M| > n é também PL completo. Por outro lado, testar se o permanente de uma matriz é positiva é PP completo. PLPL=PL no sentido de que para cada f em PL, PL é inalterada se for alargada para x→f(A,x) como uma subrotina, onde A é a string de entrada. PL contém NL e BPL , e está contida em NC2. (pt)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 56 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software