計算複雑性理論における線形加速定理(せんけいかそくていり、英: linear speedup theorem)とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。
Property | Value |
---|---|
dbo:abstract |
|
dbo:wikiPageID |
|
dbo:wikiPageLength |
|
dbo:wikiPageRevisionID |
|
dbo:wikiPageWikiLink | |
prop-ja:wikiPageUsesTemplate | |
dct:subject | |
rdfs:comment |
|
rdfs:label |
|
owl:sameAs | |
prov:wasDerivedFrom | |
foaf:isPrimaryTopicOf | |
is dbo:wikiPageWikiLink of | |
is owl:sameAs of | |
is foaf:primaryTopic of |