Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q4800823> ?p ?o }
Showing triples 1 to 28 of
28
with 100 triples per page.
- Q4800823 subject Q7452210.
- Q4800823 abstract "In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by Babai (1985). Goldwasser & Sipser (1986) proved that all languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.The basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover); but Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least 2⁄3 of the time, and if whenever the answer is "no", Arthur will never accept more than 1⁄3 of the time. Thus, Arthur acts as a probabilistic polynomial-time verifier, assuming it is allotted polynomial time to make its decisions and queries.".
- Q4800823 wikiPageExternalLink ST05.
- Q4800823 wikiPageExternalLink complexity.
- Q4800823 wikiPageWikiLink Q1143357.
- Q4800823 wikiPageWikiLink Q1563053.
- Q4800823 wikiPageWikiLink Q1665886.
- Q4800823 wikiPageWikiLink Q191943.
- Q4800823 wikiPageWikiLink Q205084.
- Q4800823 wikiPageWikiLink Q2103021.
- Q4800823 wikiPageWikiLink Q228206.
- Q4800823 wikiPageWikiLink Q3262192.
- Q4800823 wikiPageWikiLink Q3738036.
- Q4800823 wikiPageWikiLink Q4047721.
- Q4800823 wikiPageWikiLink Q4686786.
- Q4800823 wikiPageWikiLink Q500716.
- Q4800823 wikiPageWikiLink Q5973158.
- Q4800823 wikiPageWikiLink Q628036.
- Q4800823 wikiPageWikiLink Q685140.
- Q4800823 wikiPageWikiLink Q7117817.
- Q4800823 wikiPageWikiLink Q7388242.
- Q4800823 wikiPageWikiLink Q7452210.
- Q4800823 wikiPageWikiLink Q7525845.
- Q4800823 wikiPageWikiLink Q796890.
- Q4800823 wikiPageWikiLink Q908207.
- Q4800823 wikiPageWikiLink Q912887.
- Q4800823 comment "In computational complexity theory, an Arthur–Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). This notion was introduced by Babai (1985).".
- Q4800823 label "Arthur–Merlin protocol".