About: Blum's speedup theorem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Message106598915, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FBlum%27s_speedup_theorem

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

AttributesValues
rdf:type
rdfs:label
  • Blum's speedup theorem
  • Teorema del aumento de velocidad de Blum
  • ブラムの加速定理
  • Teorema dello speedup di Blum
  • Teorema da aceleração de Blum
rdfs:comment
  • En Teoría de la complejidad computacional el teorema del aumento de velocidad de Blum, dado primero por Manuel Blum en 1967, es un teorema importante sobre la complejidad de funciones computables. Cada función computable tiene un número infinito de representaciones en cierto lenguaje de programación. En la , uno suele tener que encontrar el programa con la menor complejidad por una función computable dada y una medida de complejidad. El teorema del aumento de velocidad de Blum dice que por cualquier medida de complejidad hay funciones computables que no tienen un programa mínimo.
  • ブラムの加速定理(ぶらむのかそくていり、英: Blum's speedup theorem)は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム(最適なプログラム)を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。
  • 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
  • Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili. Ogni funzione calcolabile ha un infinito numero di differenti rappresentazioni in un dato linguaggio di programmazione. Nella teoria della computabilità si ha spesso la necessità di trovare un algoritmo di minor complessità per una data funzione calcolabile e una data classe di complessità.
  • Na teoria da complexidade computacional, o teorema da aceleração de Blum ou teorema do aumento da velocidade de Blum (do inglês, Blum's speedup theorem), inicialmente definido por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis.
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
title
  • Blum's Speed-Up Theorem
urlname
  • BlumsSpeed-UpTheorem
has 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.
  • En Teoría de la complejidad computacional el teorema del aumento de velocidad de Blum, dado primero por Manuel Blum en 1967, es un teorema importante sobre la complejidad de funciones computables. Cada función computable tiene un número infinito de representaciones en cierto lenguaje de programación. En la , uno suele tener que encontrar el programa con la menor complejidad por una función computable dada y una medida de complejidad. El teorema del aumento de velocidad de Blum dice que por cualquier medida de complejidad hay funciones computables que no tienen un programa mínimo.
  • Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili. Ogni funzione calcolabile ha un infinito numero di differenti rappresentazioni in un dato linguaggio di programmazione. Nella teoria della computabilità si ha spesso la necessità di trovare un algoritmo di minor complessità per una data funzione calcolabile e una data classe di complessità. Il teorema dello speedup di Blum sostiene che per ogni classe di complessità esistono funzioni calcolabili per la cui elaborazione non esistono programmi più efficienti (veloci).
  • ブラムの加速定理(ぶらむのかそくていり、英: Blum's speedup theorem)は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム(最適なプログラム)を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。
  • Na teoria da complexidade computacional, o teorema da aceleração de Blum ou teorema do aumento da velocidade de Blum (do inglês, Blum's speedup theorem), inicialmente definido por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis. Cada função computável possui um número infinito de representações em programas diferentes em uma dada linguagem de programação. Na teoria dos algoritmos, muitas vezes procura-se encontrar um programa com a menor complexidade para uma dada função computável e uma medida de complexidade (tal programa poderia se denominar ótimo). O teorema da aceleração de Blum mostra que, para qualquer medida de complexidade, existem funções computáveis que não têm programas ótimos. Isto também descarta a ideia de que existe uma maneira de atribuir às funções arbitrárias as suas próprias complexidades computacionais, significando a atribuição de qualquer f da complexidade de um programa ótimo para f. É claro que isto não exclui a possibilidade de encontrar a complexidade de um programa ótimo para determinadas funções específicas.
prov:wasDerivedFrom
page length (characters) of wiki page
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is known for of
is known for of
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3319 as of Dec 29 2020, on Linux (x86_64-centos_6-linux-glibc2.12), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software