Relativized Arthur-Merlin versus Merlin-Arthur games (Q1117218)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Relativized Arthur-Merlin versus Merlin-Arthur games |
scientific article; zbMATH DE number 4091485
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Relativized Arthur-Merlin versus Merlin-Arthur games |
scientific article; zbMATH DE number 4091485 |
Statements
Relativized Arthur-Merlin versus Merlin-Arthur games (English)
0 references
1989
0 references
Arthur-Merlin games (introduced by L. Babai) give rise to two new complexity classes, AM and MA, depending on who starts the communication. One knows that MA \(\subset AM\). In the present paper the author constructs an oracle C such that \(MA^ C\neq AM^ C\). The proof is modelled upon \textit{Th. P. Baker} and \textit{A. L. Selman} [Theor. Comput. Sci. 8, 177-187 (1977; Zbl 0397.03023)].
0 references
Arthur-Merlin games
0 references
complexity classes
0 references
oracle
0 references
