Blum's speedup theorem (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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 exists a computable function, such that there is no optimal program computing it, because every program has a program of lower complexity. 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) 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. (es) 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). (it) ブラムの加速定理（ぶらむのかそくていり、英: Blum's speedup theorem）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。 (ja) 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. (pt) 在計算複雜性理論，布盧姆加速定理（英語：Blum's speedup theorem）為關於可计算函数複雜度的基本定理，最早由曼纽尔·布卢姆在1967年提出。 選定一種編程語言後，每個可計算函數仍由無窮多個程式實現，該些程式可能各有優劣。給定某個可計算函數和複雜度衡量時，算法理論經常尋找計算該函數「最不複雜」的算法（稱為「最優」，例如當複雜度用時間衡量時，便是「最快」）。布魯姆加速定理斷言，任何複雜度衡量下，都存在某個没有最優算法的可計算函數，亦即，任何該函數的程式實現都會比另一個實現複雜。此結論同時說明，無法同時定義全部可計算函數的複雜度（函數的複雜度是其最優程式的複雜度）。當然，不排除能找到特定函數的最優程式，並計算其複雜度。 (zh) |
| dbo:wikiPageExternalLink | http://port70.net/~nsz/articles/classic/blum_complexity_1976.pdf |
| dbo:wikiPageID | 2757528 (xsd:integer) |
| dbo:wikiPageLength | 3054 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112970923 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Computable_function dbc:Theorems_in_computational_complexity_theory dbr:Computational_complexity_theory dbr:Gödel's_speed-up_theorem dbr:Almost_all dbr:Journal_of_the_ACM dbr:Manuel_Blum dbr:Boolean_valued_function dbr:Blum_complexity_measure dbr:Computable_predicate |
| dbp:title | Blum's Speed-Up Theorem (en) |
| dbp:urlname | BlumsSpeed-UpTheorem (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:MathWorld dbt:Short_description |
| dcterms:subject | dbc:Theorems_in_computational_complexity_theory |
| gold:hypernym | dbr:Theorem |
| rdf:type | yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| 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. (es) ブラムの加速定理（ぶらむのかそくていり、英: Blum's speedup theorem）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。 (ja) 在計算複雜性理論，布盧姆加速定理（英語：Blum's speedup theorem）為關於可计算函数複雜度的基本定理，最早由曼纽尔·布卢姆在1967年提出。 選定一種編程語言後，每個可計算函數仍由無窮多個程式實現，該些程式可能各有優劣。給定某個可計算函數和複雜度衡量時，算法理論經常尋找計算該函數「最不複雜」的算法（稱為「最優」，例如當複雜度用時間衡量時，便是「最快」）。布魯姆加速定理斷言，任何複雜度衡量下，都存在某個没有最優算法的可計算函數，亦即，任何該函數的程式實現都會比另一個實現複雜。此結論同時說明，無法同時定義全部可計算函數的複雜度（函數的複雜度是其最優程式的複雜度）。當然，不排除能找到特定函數的最優程式，並計算其複雜度。 (zh) 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 exists a computable function, such that there is no optimal program computing it, because every program has a program of lower complexity. This also rules out the idea there is a way to assign to arbitrary functions their computational complexity, (en) 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à. (it) 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. (pt) |
| rdfs:label | Blum's speedup theorem (en) Teorema del aumento de velocidad de Blum (es) Teorema dello speedup di Blum (it) ブラムの加速定理 (ja) Teorema da aceleração de Blum (pt) 布盧姆加速定理 (zh) |
| owl:sameAs | freebase:Blum's speedup theorem yago-res:Blum's speedup theorem wikidata:Blum's speedup theorem dbpedia-es:Blum's speedup theorem dbpedia-it:Blum's speedup theorem dbpedia-ja:Blum's speedup theorem dbpedia-pt:Blum's speedup theorem dbpedia-zh:Blum's speedup theorem https://global.dbpedia.org/id/hkdi |
| prov:wasDerivedFrom | wikipedia-en:Blum's_speedup_theorem?oldid=1112970923&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Blum's_speedup_theorem |
| is dbo:knownFor of | dbr:Manuel_Blum |
| is dbo:wikiPageDisambiguates of | dbr:Blum |
| is dbo:wikiPageRedirects of | dbr:Blum's_speed-up_theorem dbr:Blum_speed-up_theorem dbr:Blum_speedup_theorem dbr:Blum’s_Speed-up_Theorem |
| is dbo:wikiPageWikiLink of | dbr:Blum_axioms dbr:Computational_complexity_theory dbr:Gap_theorem dbr:Gödel's_speed-up_theorem dbr:Blum dbr:Blum's_speed-up_theorem dbr:Asymptotically_optimal_algorithm dbr:Manuel_Blum dbr:List_of_theorems dbr:Speedup_theorem dbr:Blum_speed-up_theorem dbr:Blum_speedup_theorem dbr:Blum’s_Speed-up_Theorem |
| is dbp:knownFor of | dbr:Manuel_Blum |
| is foaf:primaryTopic of | wikipedia-en:Blum's_speedup_theorem |