En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada. En otras palabras, polyL = DSPACE, donde n denota el tamaño de la entrada, y O(1) es una constante. A diferencia de la clase L, que está contenida en P, no se sabe si polyL esté contenida en P, o viceversa. Por otra parte, sabemos que polyL ≠ P.

rdfs:comment
  • En complejidad computacional, PolyL es una clase de complejidad que contiene aquellos lenguajes para los cuales existe un algoritmo determinista cuyo espacio de decisión requerido está acotado por un polilogaritmo en función del tamaño de la entrada. En otras palabras, polyL = DSPACE, donde n denota el tamaño de la entrada, y O(1) es una constante. A diferencia de la clase L, que está contenida en P, no se sabe si polyL esté contenida en P, o viceversa. Por otra parte, sabemos que polyL ≠ P. (es)
foaf:isPrimaryTopicOf
rdfs:label
  • PolyL (es)
Is foaf:primaryTopic of
dcterms:subject
prov:wasDerivedFrom
dbpedia-owl:wikiPageID
  • 3926580 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 827 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 9 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 65285976 (xsd:integer)
prop-latam:wikiPageUsesTemplate
dbpedia-owl:wikiPageWikiLink
Is dbpedia-owl:wikiPageWikiLink of