This HTML5 document contains 37 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/
n18http://link.springer.com/chapter/10.1007/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
n15http://www.sciencedirect.com/science/article/pii/S002200000191774X/
n14http://cjtcs.cs.uchicago.edu/articles/1997/1/
n13http://people.csail.mit.edu/mip/papers/sat-lbs/
n11http://www.sciencedirect.com/science/article/pii/S0022000000917276/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n7http://ja.dbpedia.org/resource/Category:
wikipedia-jahttp://ja.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://knowledgecenter.siam.org/0236-000085/0236-000085/1%7Carxiv=1203.1754%7Carchiveurl=https:/archive.is/20130416012824/http:/knowledgecenter.siam.org/0236-000085/0236-000085/
n21http://www.siam.org/proceedings/soda/2011/
dbpedia-jahttp://ja.dbpedia.org/resource/
n16http://www.win.tue.nl/~gwoegi/papers/
prop-jahttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-wikidata:Q5421532
owl:sameAs
dbpedia-ja:指数時間仮説
Subject Item
dbpedia-ja:指数時間仮説
rdfs:label
指数時間仮説
rdfs:comment
計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。
dct:subject
n7:計算複雑性理論 n7:予想 n7:数学に関する記事
dbo:wikiPageID
3235394
dbo:wikiPageRevisionID
65813120
dbo:wikiPageWikiLink
dbpedia-ja:充足可能性問題 dbpedia-ja:P≠NP予想 dbpedia-ja:計算複雑性理論 dbpedia-ja:単調増加数列 n7:計算複雑性理論 dbpedia-ja:連言標準形 dbpedia-ja:NP完全問題 n7:数学に関する記事 n7:予想
dbo:wikiPageExternalLink
n11:pdf%3Fmd5=39d2ff12235e7d6a04f914120956cb5d&pid=1-s2.0-S0022000000917276-main.pdf n13:paper.pdf n14:contents.html n15:pdf%3Fmd5=dc03cf0d053a9fdab68b769ab65c28fd&pid=1-s2.0-S002200000191774X-main.pdf n16:exact.pdf n17:1%7Carchivedate=2013%E5%B9%B44%E6%9C%8816%E6%97%A5%7Cdeadlinkdate=2017%E5%B9%B410%E6%9C%88 n18:978-3-642-17517-6_3 n21:SODA11_060_lokshtanovd.pdf
prop-ja:wikiPageUsesTemplate
template-ja:Harvtxt template-ja:Math-stub template-ja:Citation template-ja:Reflist template-ja:仮リンク template-ja:Citeseerx
foaf:isPrimaryTopicOf
wikipedia-ja:指数時間仮説
dbo:abstract
計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。
dbo:wikiPageLength
6576
prov:wasDerivedFrom
wikipedia-ja:指数時間仮説?oldid=65813120&ns=0
Subject Item
dbpedia-ja:数学上の未解決問題
dbo:wikiPageWikiLink
dbpedia-ja:指数時間仮説
Subject Item
wikipedia-ja:指数時間仮説
foaf:primaryTopic
dbpedia-ja:指数時間仮説