This HTML5 document contains 85 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-enhttp://ja.dbpedia.org/resource/Template:
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-wikidatahttp://wikidata.dbpedia.org/resource/
n4https://web.archive.org/web/20061128071923/http:/qwiki.caltech.edu/wiki/
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#
n8http://ja.dbpedia.org/resource/Category:
n13http://www.cs.uchicago.edu/groups/theory/merlin/
n6http://ja.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-jahttp://ja.dbpedia.org/resource/
prop-enhttp://ja.dbpedia.org/property/

Statements

Subject Item
dbpedia-ja:NEXPTIME
dbo:wikiPageWikiLink
dbpedia-ja:対話型証明系
Subject Item
dbpedia-ja:PCP_(計算複雑性理論)
dbo:wikiPageWikiLink
dbpedia-ja:対話型証明系
Subject Item
dbpedia-ja:PSPACE
dbo:wikiPageWikiLink
dbpedia-ja:対話型証明系
Subject Item
dbpedia-ja:TQBF問題
dbo:wikiPageWikiLink
dbpedia-ja:対話型証明系
Subject Item
dbpedia-wikidata:Q1665886
owl:sameAs
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:対話型証明系
Subject Item
dbpedia-ja:対話型証明系
rdfs:label
対話型証明系
rdfs:comment
対話型証明系(たいわがたしょうめいけい、英: Interactive proof system)は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。 * 完全性: 文が真である場合、プロトコルに正しく従う検証者は、プロトコルに正しく従う証明者の証明に納得する。 * 健全性: 文が偽である場合、証明者がプロトコルに正しく従うかどうかに関わらず、プロトコルに正しく従う検証者は証明者の(真であるという)証明には従わない(小さな確率で納得してしまう可能性はある)。 なお、検証者がプロトコルに従わない場合は問題とはされず、常に検証者を信じるという点に注意されたい。
owl:sameAs
freebase:m.0155cl
dct:subject
n8:計算複雑性理論 n8:数学に関する記事
dbo:wikiPageID
1127503
dbo:wikiPageRevisionID
89936750
dbo:wikiPageWikiLink
dbpedia-ja:NP完全問題 dbpedia-ja:チューリングマシン dbpedia-ja:近似アルゴリズム dbpedia-ja:PSPACE n8:数学に関する記事 dbpedia-ja:PCP定理 dbpedia-ja:グラフ同型 dbpedia-ja:グラフ理論 dbpedia-ja:計算複雑性理論 dbpedia-ja:BPP_(計算複雑性理論) dbpedia-ja:計算資源 dbpedia-ja:IP_(計算複雑性理論) dbpedia-ja:健全性 n8:計算複雑性理論 dbpedia-ja:暗号理論 dbpedia-ja:シャフィ・ゴールドワッサー dbpedia-ja:RP_(計算複雑性理論) dbpedia-ja:P_(計算複雑性理論) dbpedia-ja:アディ・シャミア dbpedia-ja:複雑性クラス dbpedia-ja:一方向性関数 dbpedia-ja:形式言語 dbpedia-ja:P≠NP予想 dbpedia-ja:NP dbpedia-ja:ランダムアクセス dbpedia-ja:確率的チューリング機械 dbpedia-ja:非決定性チューリング機械 dbpedia-ja:PCP_(計算複雑性理論) dbpedia-ja:ゼロ知識証明 dbpedia-ja:NEXPTIME dbpedia-ja:計算模型
dbo:wikiPageExternalLink
n4:Complexity_Zoo%23ipp n4:Complexity_Zoo%23ma n4:Complexity_Zoo%23mae n4:Complexity_Zoo%23maexp n4:Complexity_Zoo%23qmalog n4:Complexity_Zoo%23qmam n4:Complexity_Zoo%23qip2 n4:Complexity_Zoo%23qma n4:Complexity_Zoo%23qma+ n4:Complexity_Zoo%23qma2 n4:Complexity_Zoo%23am n13: n4:Complexity_Zoo%23coam n4:Complexity_Zoo%23compip n4:Complexity_Zoo%23frip n4:Complexity_Zoo%23ip n4:Complexity_Zoo%23amexp n4:Complexity_Zoo%23amicoam n4:Complexity_Zoo%23ampolylog n4:Complexity_Zoo%23bpnp n4:Complexity_Zoo%23maprime n4:Complexity_Zoo%23mip n4:Complexity_Zoo%23pcp n4:Complexity_Zoo%23qip
prop-en:wikiPageUsesTemplate
template-en:Cite_book template-en:脚注ヘルプ template-en:Reflist template-en:複雑性クラス template-en:Lang-en-short
dbo:abstract
対話型証明系(たいわがたしょうめいけい、英: Interactive proof system)は、2者間のメッセージ交換によって計算をモデル化した計算模型であり、計算複雑性理論で使われる。2者とは、検証者と証明者と呼ばれ、与えられた文字列がある形式言語に属するか否かをメッセージのやり取りによって決定するものである。証明者は無限の計算資源を持つ全能の計算能力を持つが、検証者の方は限定的な計算能力を持つ。メッセージのやり取りは、検証者が証明者による証明に納得して正しいと判断するまで続けられる。 対話型証明系は、必ず次のような2つの要求に従う。 * 完全性: 文が真である場合、プロトコルに正しく従う検証者は、プロトコルに正しく従う証明者の証明に納得する。 * 健全性: 文が偽である場合、証明者がプロトコルに正しく従うかどうかに関わらず、プロトコルに正しく従う検証者は証明者の(真であるという)証明には従わない(小さな確率で納得してしまう可能性はある)。 なお、検証者がプロトコルに従わない場合は問題とはされず、常に検証者を信じるという点に注意されたい。 この系の特徴や関連する複雑性クラスが認識する言語の特徴は、検証者がどのように制限されるかに依存し、また検証者にどのような能力を与えるかに依存する。例えば、多くの対話型証明系は検証者の無作為選択能力に大きく依存する。交換されるメッセージの性質、その頻度や内容も重要である。対話型証明系は、それまで単一の機械で定義されてきた複雑性クラスに多大な影響を与えた。対話型証明系を使って定義された主な複雑性クラス(実際には複雑性クラスの階層)としては、AM、MA、、PCP などがある。
dbo:wikiPageLength
11360
prov:wasDerivedFrom
n6:対話型証明系?oldid=89936750&ns=0
foaf:isPrimaryTopicOf
n6:対話型証明系
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:Arthur–Merlinプロトコル
dbo:wikiPageWikiLink
dbpedia-ja:対話型証明系
Subject Item
n6:対話型証明系
foaf:primaryTopic
dbpedia-ja:対話型証明系