This HTML5 document contains 39 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/
n5http://qwiki.caltech.edu/wiki/
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:EXPSPACE
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:EXPTIME
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:NEXPTIME
rdfs:label
NEXPTIME
rdfs:comment
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合はNP完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、P=NP であった場合、NEXPTIME=EXPTIME となることに注意されたい。
owl:sameAs
freebase:m.030wh5
dct:subject
n4:数学に関する記事 n4:計算複雑性理論
dbo:wikiPageID
1116412
dbo:wikiPageRevisionID
65919886
dbo:wikiPageWikiLink
dbpedia-ja:ランダウの記号 dbpedia-ja:非決定性チューリング機械 dbpedia-ja:確率的検査可能証明 dbpedia-ja:決定問題 n4:数学に関する記事 dbpedia-ja:対話型証明系 dbpedia-ja:ハミルトン路 n4:計算複雑性理論 dbpedia-ja:複雑性クラス dbpedia-ja:NTIME dbpedia-ja:計算複雑性理論 dbpedia-ja:PCP_(計算複雑性理論) dbpedia-ja:隣接行列 dbpedia-ja:NP完全問題 dbpedia-ja:P≠NP予想
dbo:wikiPageExternalLink
n5:Complexity_Zoo%23conexp n5:Complexity_Zoo%23nexp
prop-ja:wikiPageUsesTemplate
template-ja:複雑性クラス template-ja:Reflist
foaf:isPrimaryTopicOf
wikipedia-ja:NEXPTIME
dbo:abstract
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。 NTIMEの記法では以下のように表される。 重要な NEXPTIME完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合はNP完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、NEXPTIME完全となる。例えば、succinct circuit を使ってグラフのハミルトン路を探す問題は NEXPTIME完全である。 なお、P=NP であった場合、NEXPTIME=EXPTIME となることに注意されたい。
dbo:wikiPageLength
1971
prov:wasDerivedFrom
wikipedia-ja:NEXPTIME?oldid=65919886&ns=0
Subject Item
dbpedia-ja:NP
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:NTIME
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:PCP_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:対話型証明系
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-ja:複雑性クラス
dbo:wikiPageWikiLink
dbpedia-ja:NEXPTIME
Subject Item
dbpedia-wikidata:Q1575791
owl:sameAs
dbpedia-ja:NEXPTIME
Subject Item
wikipedia-ja:NEXPTIME
foaf:primaryTopic
dbpedia-ja:NEXPTIME