Metraipolis › archive › dc_8895bb3615de

Arthur–Merlin protocol — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-05T23:25:10.709Z
SHA-256 of the archived text
7889a4a517e0608b4946c833e857e0587dd9cbe6a3d34174a0b114e056a12f13
Stable URL of this page
https://metraipolis.com/documento/dc_8895bb3615de

How to cite

Arthur–Merlin protocol — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8895bb3615de (Metraipolis archive dc_8895bb3615de, sha256 7889a4a517e0608b4946c833e857e0587dd9cbe6a3d34174a0b114e056a12f13)
BibTeX
@misc{dc8895bb3615de,
  title = {Arthur–Merlin protocol — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8895bb3615de; sha256 7889a4a517e0608b4946c833e857e0587dd9cbe6a3d34174a0b114e056a12f13},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. Given two participants in the protocol called Arthur and Merlin respectively, 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). However, 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.

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «zero-knowledge proof»).
Fonte: Wikipedia in inglese, voce «Arthur–Merlin protocol» — https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol
Wikidata Q4800823 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4800823
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Arthur%E2%80%93Merlin_protocol?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1356300537, consultata il 2026-10-05T23:07:33.636Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9d374eb239c20f3ef6efd39b63773f95fc5b0ba5fe932ee86ad44e61c7c571e7