Linear speedup theorem (original) (raw)
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1.If the original machine is non-deterministic, then the new machine is also non-deterministic.The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1.If the original machine is non-deterministic, then the new machine is also non-deterministic.The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2. (en) El teorema del incremento lineal de velocidad de las máquinas de Turing es un teorema de teoría de la complejidad computacional, que se puede enunciar: (es) Le théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique. On peut en fait distinguer deux théorèmes, l'un concernant les classes de complexité en espace et l'autre les classes de complexité en temps. Tous deux ont pour conséquence de regrouper les mesures de complexité qui ne diffèrent que d'une constante, et justifie donc la notation grand O utilisée dans le domaine. Le théorème de d'accélération en temps est dû à Juris Hartmanis et Richard Stearns. (fr) 計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。 (ja) O teorema da aceleração linear ou speedup linear é um teorema da teoria da complexidade, um campo da teoria da computação. Pode-se distinguir dois teoremas: uma que diz respeito às classes de complexidade referentes ao espaço e outro que diz respeito às classes de complexidade de tempo. Ambos têm como consequência agrupar as medidas de complexidade que diferem apenas por uma constante, e, portanto, justifica a notação O utilizada no campo. O teorema da aceleração do tempo foi provado por Juris Hartmanis e Richard Stearns. (pt) 在计算复杂性理论中，图灵机的线性加速定理是指：给定任意实数 c > 0 ，如果有任意图灵机在 f(n) 时间内可以解决一个问题 L 则一定存在另一个图灵机可以在 cf(n) + n + 2 的时间内解决这个问题 L。 (zh) |
| dbo:wikiPageID | 663023 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Speedup-Theorem |
| dbo:wikiPageLength | 5476 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1065051721 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Theorems_in_computational_complexity_theory dbr:Computational_complexity_theory dbr:Non-deterministic_Turing_machine dbr:Real_number dbr:Turing_machine |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Theorems_in_computational_complexity_theory |
| rdf:type | yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1.If the original machine is non-deterministic, then the new machine is also non-deterministic.The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2. (en) El teorema del incremento lineal de velocidad de las máquinas de Turing es un teorema de teoría de la complejidad computacional, que se puede enunciar: (es) Le théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique. On peut en fait distinguer deux théorèmes, l'un concernant les classes de complexité en espace et l'autre les classes de complexité en temps. Tous deux ont pour conséquence de regrouper les mesures de complexité qui ne diffèrent que d'une constante, et justifie donc la notation grand O utilisée dans le domaine. Le théorème de d'accélération en temps est dû à Juris Hartmanis et Richard Stearns. (fr) 計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。 (ja) O teorema da aceleração linear ou speedup linear é um teorema da teoria da complexidade, um campo da teoria da computação. Pode-se distinguir dois teoremas: uma que diz respeito às classes de complexidade referentes ao espaço e outro que diz respeito às classes de complexidade de tempo. Ambos têm como consequência agrupar as medidas de complexidade que diferem apenas por uma constante, e, portanto, justifica a notação O utilizada no campo. O teorema da aceleração do tempo foi provado por Juris Hartmanis e Richard Stearns. (pt) 在计算复杂性理论中，图灵机的线性加速定理是指：给定任意实数 c > 0 ，如果有任意图灵机在 f(n) 时间内可以解决一个问题 L 则一定存在另一个图灵机可以在 cf(n) + n + 2 的时间内解决这个问题 L。 (zh) |
| rdfs:label | Teorema del incremento lineal de velocidad (es) Théorème d'accélération linéaire (fr) Linear speedup theorem (en) 線形加速定理 (ja) Teorema da aceleração linear (pt) 线性加速定理 (zh) |
| owl:sameAs | freebase:Linear speedup theorem yago-res:Linear speedup theorem wikidata:Linear speedup theorem dbpedia-es:Linear speedup theorem dbpedia-fr:Linear speedup theorem dbpedia-ja:Linear speedup theorem dbpedia-pt:Linear speedup theorem dbpedia-zh:Linear speedup theorem https://global.dbpedia.org/id/3Fd8W |
| prov:wasDerivedFrom | wikipedia-en:Linear_speedup_theorem?oldid=1065051721&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Linear_speedup_theorem |
| is dbo:wikiPageRedirects of | dbr:Tape_compression_theorem |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:Linear_bounded_automaton dbr:List_of_theorems dbr:Speedup_theorem dbr:Tape_compression_theorem |
| is foaf:primaryTopic of | wikipedia-en:Linear_speedup_theorem |