This HTML5 document contains 23 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
template-enhttp://ja.dbpedia.org/resource/Template:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://ja.dbpedia.org/resource/Category:
owlhttp://www.w3.org/2002/07/owl#
n11http://ja.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-enhttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-ja:加速定理
dbo:wikiPageWikiLink
dbpedia-ja:線形加速定理
Subject Item
dbpedia-ja:線形加速定理
rdfs:label
線形加速定理
rdfs:comment
計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。
owl:sameAs
freebase:m.030tbz
dct:subject
n6:計算複雑性理論の定理 n6:数学に関する記事
dbo:wikiPageID
3047620
dbo:wikiPageRevisionID
55387524
dbo:wikiPageWikiLink
n6:計算複雑性理論の定理 dbpedia-ja:加速定理 dbpedia-ja:テープ圧縮定理 dbpedia-ja:チューリング機械 n6:数学に関する記事 dbpedia-ja:計算複雑性理論 dbpedia-ja:形式言語
prop-en:wikiPageUsesTemplate
template-en:Lang-en-short template-en:Reflist
dbo:abstract
計算複雑性理論における線形加速定理（せんけいかそくていり、英: linear speedup theorem）とは、与えられたチューリング機械に対して、同じ問題を解くより高速なチューリング機械の存在を述べる定理である。より正確に述べると次の通りである。任意の正の定数 c と時間量 f(n) で言語を決定するチューリング機械 M に対して、M と同じ言語を決定するチューリング機械 M' で時間量が高々 cf(n) + n + 2 であるようなものが存在する。
dbo:wikiPageLength
1382
prov:wasDerivedFrom
n11:線形加速定理?oldid=55387524&ns=0
foaf:isPrimaryTopicOf
n11:線形加速定理
Subject Item
dbpedia-wikidata:Q3527226
owl:sameAs
dbpedia-ja:線形加速定理
Subject Item
n11:線形加速定理
foaf:primaryTopic
dbpedia-ja:線形加速定理