Relativized Arthur-Merlin versus Merlin-Arthur games

摘要: Arthur-Merlin games were introduced recently by Babai in order to capture the intuitive notion of efficient, probabilistic proof-systems. Considered as complexity classes, they are extensions NP. It turned out, that one exchange messages between two players is sufficient simulate a constant number interactions. Thus at most new classes survive levels this hierarchy: AM and MA, depending on who starts communication. known \(MA \subseteq AM\). In paper we answer an open problem Babai: construct oracle C such \(AM^C - \Sigma _2^{P,C} \ne \emptyset\). Since \(MA^C _2^{P,C}\), it follows for some C, MAC≠AMC. Our prooftechnique modification technique used Baker Selman show ∑ 2 P ∏ can be separated oracle. This result interpreted evidence with messages, proof-system stronger when Arthur