Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Blums_speedup_theorem> ?p ?o }
Showing triples 1 to 43 of
43
with 100 triples per page.
- Blums_speedup_theorem abstract "In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions. Each computable function has an infinite number of different program representations in a given programming language. In the theory of algorithms one often strives to find a program with the smallest complexity for a given computable function and a given complexity measure (such a program could be called optimal). Blum's speedup theorem shows that for any complexity measure there are computable functions that are not optimal with respect to that measure. This also rules out the idea there is a way to assign to arbitrary functions their computational complexity, meaning the assignment to any f of the complexity of an optimal program for f. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions.".
- Blums_speedup_theorem wikiPageExternalLink blum_complexity_1976.pdf.
- Blums_speedup_theorem wikiPageID "2757528".
- Blums_speedup_theorem wikiPageLength "2898".
- Blums_speedup_theorem wikiPageOutDegree "13".
- Blums_speedup_theorem wikiPageRevisionID "680890422".
- Blums_speedup_theorem wikiPageWikiLink Algorithm.
- Blums_speedup_theorem wikiPageWikiLink Almost_all.
- Blums_speedup_theorem wikiPageWikiLink Blum_axioms.
- Blums_speedup_theorem wikiPageWikiLink Blum_complexity_measure.
- Blums_speedup_theorem wikiPageWikiLink Boolean_function.
- Blums_speedup_theorem wikiPageWikiLink Boolean_valued_function.
- Blums_speedup_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- Blums_speedup_theorem wikiPageWikiLink Complexity_measure.
- Blums_speedup_theorem wikiPageWikiLink Computable_function.
- Blums_speedup_theorem wikiPageWikiLink Computable_predicate.
- Blums_speedup_theorem wikiPageWikiLink Computational_complexity_theory.
- Blums_speedup_theorem wikiPageWikiLink Gxc3xb6dels_speed-up_theorem.
- Blums_speedup_theorem wikiPageWikiLink Journal_of_the_ACM.
- Blums_speedup_theorem wikiPageWikiLink Manuel_Blum.
- Blums_speedup_theorem wikiPageWikiLink Speedup_theorem.
- Blums_speedup_theorem wikiPageWikiLink Speedup_theorem_(disambiguation).
- Blums_speedup_theorem wikiPageWikiLinkText "Blum's speedup theorem".
- Blums_speedup_theorem wikiPageWikiLinkText "Speedup".
- Blums_speedup_theorem wikiPageWikiLinkText "speed-up theorem".
- Blums_speedup_theorem hasPhotoCollection Blums_speedup_theorem.
- Blums_speedup_theorem title "Blum's Speed-Up Theorem".
- Blums_speedup_theorem urlname "BlumsSpeed-UpTheorem".
- Blums_speedup_theorem wikiPageUsesTemplate Template:Cite_journal.
- Blums_speedup_theorem wikiPageUsesTemplate Template:MathWorld.
- Blums_speedup_theorem subject Category:Theorems_in_computational_complexity_theory.
- Blums_speedup_theorem hypernym Theorem.
- Blums_speedup_theorem comment "In computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions. Each computable function has an infinite number of different program representations in a given programming language. In the theory of algorithms one often strives to find a program with the smallest complexity for a given computable function and a given complexity measure (such a program could be called optimal).".
- Blums_speedup_theorem label "Blum's speedup theorem".
- Blums_speedup_theorem sameAs Teorema_del_aumento_de_velocidad_de_Blum.
- Blums_speedup_theorem sameAs Teorema_dello_speedup_di_Blum.
- Blums_speedup_theorem sameAs ブラムの加速定理.
- Blums_speedup_theorem sameAs Teorema_da_aceleração_de_Blum.
- Blums_speedup_theorem sameAs m.080_2y.
- Blums_speedup_theorem sameAs Q1751105.
- Blums_speedup_theorem sameAs Q1751105.
- Blums_speedup_theorem wasDerivedFrom Blums_speedup_theoremoldid=680890422.
- Blums_speedup_theorem isPrimaryTopicOf Blums_speedup_theorem.