Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Gap_theorem> ?p ?o }
Showing triples 1 to 37 of
37
with 100 triples per page.
- Gap_theorem abstract "See also Gap theorem (disambiguation) for other gap theorems in mathematics.In computational complexity theory the Gap Theorem, also known as the Borodin-Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions.It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes. For any computable function that represents an increase in computational resources, one can find a resource bound such that the set of functions computable within the expanded resource bound is the same as the set computable within the original bound.The theorem was proved independently by Boris Trakhtenbrotand Allan Borodin.".
- Gap_theorem wikiPageID "2815277".
- Gap_theorem wikiPageLength "4053".
- Gap_theorem wikiPageOutDegree "18".
- Gap_theorem wikiPageRevisionID "671317396".
- Gap_theorem wikiPageWikiLink Allan_Borodin.
- Gap_theorem wikiPageWikiLink Blum_axioms.
- Gap_theorem wikiPageWikiLink Blums_speedup_theorem.
- Gap_theorem wikiPageWikiLink Boris_Trakhtenbrot.
- Gap_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- Gap_theorem wikiPageWikiLink Complexity_class.
- Gap_theorem wikiPageWikiLink Computable_function.
- Gap_theorem wikiPageWikiLink Computational_complexity_theory.
- Gap_theorem wikiPageWikiLink Computational_model.
- Gap_theorem wikiPageWikiLink Computational_resource.
- Gap_theorem wikiPageWikiLink Constructible_function.
- Gap_theorem wikiPageWikiLink Gap_theorem_(disambiguation).
- Gap_theorem wikiPageWikiLink Mathematics.
- Gap_theorem wikiPageWikiLink Space_hierarchy_theorem.
- Gap_theorem wikiPageWikiLink Time_hierarchy_theorem.
- Gap_theorem wikiPageWikiLinkText "Gap theorem".
- Gap_theorem wikiPageWikiLinkText "Gap".
- Gap_theorem wikiPageWikiLinkText "gap theorem".
- Gap_theorem wikiPageUsesTemplate Template:Reflist.
- Gap_theorem subject Category:Theorems_in_computational_complexity_theory.
- Gap_theorem hypernym Theorem.
- Gap_theorem type Theorem.
- Gap_theorem comment "See also Gap theorem (disambiguation) for other gap theorems in mathematics.In computational complexity theory the Gap Theorem, also known as the Borodin-Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions.It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes.".
- Gap_theorem label "Gap theorem".
- Gap_theorem sameAs Q1314081.
- Gap_theorem sameAs Lückensatz_von_Borodin.
- Gap_theorem sameAs ギャップ定理_(計算複雑性理論).
- Gap_theorem sameAs Teorema_do_intervalo.
- Gap_theorem sameAs m.084h7j.
- Gap_theorem sameAs Q1314081.
- Gap_theorem wasDerivedFrom Gap_theorem?oldid=671317396.
- Gap_theorem isPrimaryTopicOf Gap_theorem.