Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Arthur–Merlin_protocol> ?p ?o }
Showing triples 1 to 60 of
60
with 100 triples per page.
- Arthur–Merlin_protocol 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.".
- Arthur–Merlin_protocol wikiPageExternalLink ST05.
- Arthur–Merlin_protocol wikiPageExternalLink complexity.
- Arthur–Merlin_protocol wikiPageID "663203".
- Arthur–Merlin_protocol wikiPageLength "11199".
- Arthur–Merlin_protocol wikiPageOutDegree "23".
- Arthur–Merlin_protocol wikiPageRevisionID "704856188".
- Arthur–Merlin_protocol wikiPageWikiLink Advice_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink BPP_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink Cambridge_University_Press.
- Arthur–Merlin_protocol wikiPageWikiLink Category:Probabilistic_complexity_theory.
- Arthur–Merlin_protocol wikiPageWikiLink Complexity_class.
- Arthur–Merlin_protocol wikiPageWikiLink Computational_complexity_theory.
- Arthur–Merlin_protocol wikiPageWikiLink Decision_problem.
- Arthur–Merlin_protocol wikiPageWikiLink Generalized_Riemann_hypothesis.
- Arthur–Merlin_protocol wikiPageWikiLink Graph_isomorphism_problem.
- Arthur–Merlin_protocol wikiPageWikiLink IP_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink Interactive_proof_system.
- Arthur–Merlin_protocol wikiPageWikiLink NP_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink Oracle_machine.
- Arthur–Merlin_protocol wikiPageWikiLink poly.
- Arthur–Merlin_protocol wikiPageWikiLink PP_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink PSPACE.
- Arthur–Merlin_protocol wikiPageWikiLink Polynomial_hierarchy.
- Arthur–Merlin_protocol wikiPageWikiLink QMA.
- Arthur–Merlin_protocol wikiPageWikiLink Random_number_generation.
- Arthur–Merlin_protocol wikiPageWikiLink S2P_(complexity).
- Arthur–Merlin_protocol wikiPageWikiLink Sipser–Lautemann_theorem.
- Arthur–Merlin_protocol wikiPageWikiLink Zero-knowledge_proof.
- Arthur–Merlin_protocol wikiPageWikiLinkText "AM".
- Arthur–Merlin_protocol wikiPageWikiLinkText "AM ∩ co-AM".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Arthur–Merlin Games".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Arthur–Merlin protocol".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Arthur–Merlin protocol#AM".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Arthur–Merlin protocol#MA".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Arthur–Merlin_protocol".
- Arthur–Merlin_protocol wikiPageWikiLinkText "MA and AM".
- Arthur–Merlin_protocol wikiPageWikiLinkText "MA".
- Arthur–Merlin_protocol wikiPageWikiLinkText "Merlin Arthur".
- Arthur–Merlin_protocol b "2".
- Arthur–Merlin_protocol p "P".
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:CZoo.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:Citation.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:ComplexityClasses.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:Frac.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:Harvtxt.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:Reflist.
- Arthur–Merlin_protocol wikiPageUsesTemplate Template:Su.
- Arthur–Merlin_protocol subject Category:Probabilistic_complexity_theory.
- Arthur–Merlin_protocol hypernym System.
- Arthur–Merlin_protocol type Class.
- Arthur–Merlin_protocol type Redirect.
- Arthur–Merlin_protocol 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).".
- Arthur–Merlin_protocol label "Arthur–Merlin protocol".
- Arthur–Merlin_protocol sameAs Q4800823.
- Arthur–Merlin_protocol sameAs Protocole_Arthur-Merlin.
- Arthur–Merlin_protocol sameAs m.030v3k.
- Arthur–Merlin_protocol sameAs Q4800823.
- Arthur–Merlin_protocol wasDerivedFrom Arthur–Merlin_protocol?oldid=704856188.
- Arthur–Merlin_protocol isPrimaryTopicOf Arthur–Merlin_protocol.