計算複雑性理論における線形加速定理(せんけいかそくていり、英: linear speedup theorem)とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。

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