Statements (25)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
interactive proof system
|
| gptkbp:abbreviation |
MA protocol
|
| gptkbp:complexity |
gptkb:MA
|
| gptkbp:describes |
A class of interactive proof systems where Merlin sends a message to Arthur, who then flips random coins and decides to accept or reject.
|
| gptkbp:deterministicVerifier |
no
|
| gptkbp:field |
theoretical computer science
|
| gptkbp:generalizes |
NP
|
| gptkbp:hasSubgroup |
gptkb:AM
|
| https://www.w3.org/2000/01/rdf-schema#label |
Merlin-Arthur protocol
|
| gptkbp:introducedIn |
1980s
|
| gptkbp:namedAfter |
gptkb:Arthur
gptkb:Merlin |
| gptkbp:numberOfRounds |
one
|
| gptkbp:privateCoin |
yes
|
| gptkbp:prover |
gptkb:Merlin
|
| gptkbp:publicCoin |
no
|
| gptkbp:randomizedVerifier |
yes
|
| gptkbp:relatedTo |
gptkb:IP
gptkb:AM gptkb:BPP gptkb:Arthur-Merlin_protocol NP |
| gptkbp:verifier |
gptkb:Arthur
|
| gptkbp:bfsParent |
gptkb:Arthur-Merlin_protocol
|
| gptkbp:bfsLayer |
6
|