I am trying to prove that $\text{NEXP} = \text{MA} \Rightarrow \text{NEXP} \subseteq P/\text{Poly}$. I tried to approach the result via trying out the contrapositive, that $\text{NEXP} \nsubseteq P/\text{Poly} \Rightarrow \text{NEXP} \ne \text{MA}$ but I couldn't get anywhere. Can anyone give me a hint to proceed?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ It seems easier to prove it directly rather than via the contrapositive. $\endgroup$– Yuval FilmusCommented Dec 5, 2020 at 15:56
-
$\begingroup$ Can you give a hint as how to proceed in that direction? From NEXP=MA we get NEXP=EXP, what all complexity results can I get from this? $\endgroup$– roydiptajitCommented Dec 5, 2020 at 16:05
-
$\begingroup$ See Theorem 27 in IKW. $\endgroup$– Yuval FilmusCommented Dec 5, 2020 at 17:22
-
$\begingroup$ Thanks @YuvalFilmus $\endgroup$– roydiptajitCommented Dec 5, 2020 at 18:04
Add a comment
|