Lower Bounds for Swapping Arthur and Merlin

摘要: We prove a lower bound for swapping the order of Arthur and Merlin in two-round Merlin-Arthur games using black-box techniques. Namely, we show that any AM-game requires time i¾?(t2) to simulate MA-games running t. Thus, known simulations MA by AM with quadratic overhead, dating back Babai's original paper on Arthur-Merlin games, are tight within this setting. The also yields an oracle relative which ${\rm MA-TIME}[n] \nsubseteq {\rm AM-TIME}[o(n^2)]$. Complementing our bounds MA-games, time-space drop entirely. $c , there exists positive dsuch is language recognized linear-time one-sided error but not probabilistic random-access machines two-sided run ncand space nd. This improves recent results give such problems second level polynomial-time hierarchy.