Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Gap_theorem> ?p ?o. }
Showing items 1 to 24 of
24
with 100 items 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 wikiPageRevisionID "593776600".
- Gap_theorem hasPhotoCollection Gap_theorem.
- Gap_theorem subject Category:Theorems_in_computational_complexity_theory.
- Gap_theorem type Abstraction100002137.
- Gap_theorem type Communication100033020.
- Gap_theorem type Message106598915.
- Gap_theorem type Proposition106750804.
- Gap_theorem type Statement106722453.
- Gap_theorem type Theorem106752293.
- Gap_theorem type TheoremsInDiscreteMathematics.
- 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 label "Lückensatz von Borodin".
- Gap_theorem label "Teorema do intervalo".
- Gap_theorem sameAs Lückensatz_von_Borodin.
- Gap_theorem sameAs Teorema_do_intervalo.
- Gap_theorem sameAs m.084h7j.
- Gap_theorem sameAs Q1314081.
- Gap_theorem sameAs Q1314081.
- Gap_theorem sameAs Gap_theorem.
- Gap_theorem wasDerivedFrom Gap_theorem?oldid=593776600.
- Gap_theorem isPrimaryTopicOf Gap_theorem.