HTML Microdata document

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

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

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
template-en	http://ja.dbpedia.org/resource/Template:
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbpedia-wikidata	http://wikidata.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n5	http://ja.dbpedia.org/resource/Category:
n9	http://ja.wikipedia.org/wiki/
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
dbpedia-ja	http://ja.dbpedia.org/resource/
prop-en	http://ja.dbpedia.org/property/

Statements

Subject Item: dbpedia-wikidata:Q215206
owl:sameAs: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:充足可能性問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:D-Wave_Systems
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:DNAコンピュータ
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:I.Q
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NC_(計算複雑性理論)
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NEXPTIME
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NP
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NP困難
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NP完全問題
rdfs:label: NP完全問題
rdfs:comment: NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。
owl:sameAs: freebase:m.09tkl
dct:subject: n5:NP完全問題 n5:数学の問題 n5:数学に関する記事 n5:計算問題
dbo:wikiPageID: 10595
dbo:wikiPageRevisionID: 84488262
dbo:wikiPageWikiLink: dbpedia-ja:多項式時間変換 dbpedia-ja:グラフ彩色 n5:数学の問題 dbpedia-ja:NP困難 dbpedia-ja:充足可能性問題 dbpedia-ja:アルゴリズム dbpedia-ja:テトリス n5:NP完全問題 dbpedia-ja:ナップサック問題 dbpedia-ja:部分和問題 n5:数学に関する記事 dbpedia-ja:1971年 n5:計算問題 dbpedia-ja:スティーブン・クック dbpedia-ja:巡回セールスマン問題 dbpedia-ja:ハミルトン閉路問題 dbpedia-ja:頂点被覆問題 dbpedia-ja:NP dbpedia-ja:ハミルトン路 dbpedia-ja:多項式時間近似スキーム
prop-en:wikiPageUsesTemplate: template-en:複雑性クラス template-en:Reflist
dbo:abstract: NP完全（な）問題（エヌピーかんぜん（な）もんだい、NP-complete problem）とは、(1) クラスNP（Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され、R. M. カープの定義した多項式時間還元によって多くの計算量的に困難な問題が NP 完全であることが示された。
dbo:wikiPageLength: 4461
prov:wasDerivedFrom: n9:NP完全問題?oldid=84488262&ns=0
foaf:isPrimaryTopicOf: n9:NP完全問題

Subject Item: dbpedia-ja:PP_(計算複雑性理論)
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:STRIPS
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:Sharp-P
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:アルゴリズム解析
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:クリーク_(グラフ理論)
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:グラフ彩色
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ゲーム
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:コンパイラ最適化
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:シュードノット
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:シーケンスアラインメント
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:スティーブン・クック
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題
prop-en:knownFor: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:スパースモデリング
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ゼロ知識証明
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ディオファントス方程式
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ナップサック問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ハミルトン路
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ハミルトン閉路問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:ホーン節
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:レオナルド・エーデルマン
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:レジスタ割り付け
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:双対グラフ
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:四色定理
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:完全2部グラフ
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:完全性_(曖昧さ回避)
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:対数領域還元
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:対話型証明系
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:巡回セールスマン問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:平方剰余
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:折紙の数学
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:指数時間仮説
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:数学ガール
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:最小クリーク被覆問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:最短経路問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:決定的アルゴリズム
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:浜村渚の計算ノート
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:独立集合
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:神託機械
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:種数
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:線形論理
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:美術館_(パズル)
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:虫食い算
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:補グラフ
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:複雑性クラス
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:覆面算
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:計算複雑性理論
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:誘導部分グラフ
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:連言標準形
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:量子暗号
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:非決定性チューリングマシン
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:頂点被覆
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:頂点被覆問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:AI完全
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:多項式時間変換
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:最小極大マッチング問題
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:構文解析
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題

Subject Item: dbpedia-ja:NP完全
dbo:wikiPageWikiLink: dbpedia-ja:NP完全問題
dbo:wikiPageRedirects: dbpedia-ja:NP完全問題

Subject Item: n9:NP完全問題
foaf:primaryTopic: dbpedia-ja:NP完全問題