Arthur-Merlin languages are those languages recognized by the interactive proof system, in which the polynomial-time TM Arthur interacts with the untrustworthy oracle Merlin in such a way that Arthur accepts at least 2/3 of the time when Merlin's answer is correct and rejects 2/3 of the time when Merlin's answer is wrong, allowing the polynomial interaction to be run many times and producing a stastical high likelyhood of recognizing which strings are in the language.

http://cs.marlboro.edu/ courses/ fall2006/ tutorials/ chomsky_hierarchy/ Arthur_Merlin
last modified Friday December 8 2006 1:58 am EST