This HTML5 document contains 38 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-jahttp://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#
n11http://ja.dbpedia.org/resource/Category:
owlhttp://www.w3.org/2002/07/owl#
wikipedia-jahttp://ja.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-jahttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-ja:ギャップ定理_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:ゲーデルの加速定理
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:ブラム
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
dbo:wikiPageDisambiguates
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:ブラムの公理
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:ブラムの加速定理
rdfs:label
ブラムの加速定理
rdfs:comment
ブラムの加速定理（ぶらむのかそくていり、英: Blum's speedup theorem）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。
owl:sameAs
freebase:m.080_2y
dct:subject
n11:計算複雑性理論の定理 n11:数学に関する記事
dbo:wikiPageID
3047564
dbo:wikiPageRevisionID
70076749
dbo:wikiPageWikiLink
dbpedia-ja:ほとんど全ての dbpedia-ja:ゲーデルの加速定理 dbpedia-ja:加速定理 dbpedia-ja:アルゴリズム dbpedia-ja:計算可能関数 dbpedia-ja:ブラムの公理 n11:数学に関する記事 dbpedia-ja:ブール値関数 dbpedia-ja:マヌエル・ブラム dbpedia-ja:ゲーデル数 dbpedia-ja:計算複雑性理論 n11:計算複雑性理論の定理
prop-ja:wikiPageUsesTemplate
template-ja:Cite_journal template-ja:Lang-en-short template-ja:MathWorld
prop-ja:title
Blum's Speed-Up Theorem
prop-ja:urlname
BlumsSpeed-UpTheorem
dbo:abstract
ブラムの加速定理（ぶらむのかそくていり、英: Blum's speedup theorem）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対してその計算複雑性を割り当てる方法、つまり任意の関数 f に対して f を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。
dbo:wikiPageLength
1605
prov:wasDerivedFrom
wikipedia-ja:ブラムの加速定理?oldid=70076749&ns=0
foaf:isPrimaryTopicOf
wikipedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:マヌエル・ブラム
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:加速定理
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-ja:圧縮定理
dbo:wikiPageWikiLink
dbpedia-ja:ブラムの加速定理
Subject Item
dbpedia-wikidata:Q1751105
owl:sameAs
dbpedia-ja:ブラムの加速定理
Subject Item
wikipedia-ja:ブラムの加速定理
foaf:primaryTopic
dbpedia-ja:ブラムの加速定理