En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede resolver más problemas. Por ejemplo, hay problemas que pueden ser solucionados en tiempo O(n) pero no en O(n). El teorema de la jerarquía temporal para máquinas de Turing deterministas fue probado por Richard Stearns y Juris Hartmanis.
Autor | |
Año |
|
rdfs:comment |
|
Edición |
|
Editorial |
|
foaf:isPrimaryTopicOf | |
Isbn |
|
rdfs:label |
|
Is foaf:primaryTopic of | |
dcterms:subject | |
rdf:type | |
Título |
|
prov:wasDerivedFrom | |
dbpedia-owl:wikiPageID |
|
dbpedia-owl:wikiPageLength |
|
dbpedia-owl:wikiPageOutDegree |
|
Is dbpedia-owl:wikiPageRedirects of | |
dbpedia-owl:wikiPageRevisionID |
|
prop-latam:wikiPageUsesTemplate | |
dbpedia-owl:wikiPageWikiLink | [29 values] |
Is dbpedia-owl:wikiPageWikiLink of |