Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR17-031 | 15th February 2017 18:35

TR17-031
Authors: Thomas Watson
Publication: 19th February 2017 09:28
The known proofs of $\text{MA}\subseteq\text{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 $\text{MA-TIME}(t)\not\subseteq\text{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\"o\"os) that there is an oracle relative to which $\text{MA}\not\subseteq\text{NP}^{\text{BPP}}$ (which was previously known to hold by a proof using generics).