En teoría de la complejidad computacional, se dice que una función es una función de espacio constructivo si existe una Máquina de Turing que toda entrada de longitud n utiliza a lo sumo S(n) casillas (sin contar las casillas de la entrada) y además, para todo natural n existe una entrada de longitud n que utiliza exactamente S(n) casillas. Las funciones de espacio constructivo se utilizan para definir clases de complejidad acotadas por espacio.

rdfs:comment
  • En teoría de la complejidad computacional, se dice que una función es una función de espacio constructivo si existe una Máquina de Turing que toda entrada de longitud n utiliza a lo sumo S(n) casillas (sin contar las casillas de la entrada) y además, para todo natural n existe una entrada de longitud n que utiliza exactamente S(n) casillas. Las funciones de espacio constructivo se utilizan para definir clases de complejidad acotadas por espacio. (es)
foaf:isPrimaryTopicOf
rdfs:label
  • Función de espacio constructivo (es)
Is foaf:primaryTopic of
dcterms:subject
prov:wasDerivedFrom
Is dbpedia-owl:wikiPageDisambiguates of
dbpedia-owl:wikiPageID
  • 241300 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 1667 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 7 (xsd:integer)
Is dbpedia-owl:wikiPageRedirects of
dbpedia-owl:wikiPageRevisionID
  • 42463082 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
Is dbpedia-owl:wikiPageWikiLink of