This HTML5 document contains 40 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#
owlhttp://www.w3.org/2002/07/owl#
n4http://ja.dbpedia.org/resource/Category:
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:L_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:対数領域還元
Subject Item
dbpedia-ja:P_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:対数領域還元
Subject Item
dbpedia-ja:SL_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:対数領域還元
Subject Item
dbpedia-wikidata:Q448582
owl:sameAs
dbpedia-ja:対数領域還元
Subject Item
dbpedia-ja:対数領域還元
rdfs:label
対数領域還元
rdfs:comment
対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。 対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語（共に P に包含される）との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。 対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。
owl:sameAs
freebase:m.04djlk
dct:subject
n4:還元_(計算複雑性理論) n4:数学に関する記事
dbo:wikiPageID
1114738
dbo:wikiPageRevisionID
77631538
dbo:wikiPageWikiLink
n4:還元_(計算複雑性理論) n4:数学に関する記事 dbpedia-ja:P_(計算複雑性理論) dbpedia-ja:計算複雑性理論 dbpedia-ja:NC_(計算複雑性理論) dbpedia-ja:チューリングマシン dbpedia-ja:SL_(計算複雑性理論) dbpedia-ja:多対一還元 dbpedia-ja:チューリング還元 dbpedia-ja:NL_(計算複雑性理論) dbpedia-ja:還元_(計算複雑性理論) dbpedia-ja:L_(計算複雑性理論) dbpedia-ja:多項式時間変換 dbpedia-ja:NP完全問題
prop-ja:wikiPageUsesTemplate
template-ja:出典の明記 template-ja:Reflist template-ja:Lang-en-short
dbo:abstract
対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。 対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語（共に P に包含される）との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。 対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。 多項式時間還元が P やそのサブクラスではあまり意味がないのと同様、対数領域還元も L とそのサブクラスを区別するのには役立たない。L に属するほとんどの問題は、対数領域還元の下でL完全である。より弱い還元があったとしても、単に問題を L の真部分集合である言語に先延ばしするだけであるため、実際には使われることはほとんどない。 対数領域還元のためのツールは、L = SL という結果によって大きく拡張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。
foaf:isPrimaryTopicOf
wikipedia-ja:対数領域還元
dbo:wikiPageLength
1392
prov:wasDerivedFrom
wikipedia-ja:対数領域還元?oldid=77631538&ns=0
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-ja:対数空間還元
dbo:wikiPageWikiLink
dbpedia-ja:対数領域還元
dbo:wikiPageRedirects
dbpedia-ja:対数領域還元
Subject Item
dbpedia-ja:対数領域帰着
dbo:wikiPageWikiLink
dbpedia-ja:対数領域還元
dbo:wikiPageRedirects
dbpedia-ja:対数領域還元
Subject Item
wikipedia-ja:対数領域還元
foaf:primaryTopic
dbpedia-ja:対数領域還元