Arthur and Merlin

From Citizendium
Jump to navigation Jump to search
This article is developed but not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable, developed Main Article is subject to a disclaimer.

Arthur and Merlin are a pair of players (like Alice and Bob) used by László Babai in his paper Trading group theory for randomness[1] (1985) where he introduced Arthur vs. Merlin games in order to define new Arthur-Merlin complexity classes related to interactive proof systems.

  1. STOC '85 Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM. 421–429 (1985),(abstract)