Quadratic Simulations of Merlin–Arthur Games
Thomas W. Watson · ACM Transactions on Computation Theory · 2020
The known proofs of MA ⊆ PP incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which MA-TIME ( t ) ⊈ P-TIME ( o ( t 2 )). We also show that 2-sided-error Merlin–Arthur games can be simulated by 1-sided-error Arthur–Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika Göös) that there is an oracle relative to which MA ⊈ NP BPP (which was previously known to hold by a proof using generics).