6
$\begingroup$

Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?

$\endgroup$
5
$\begingroup$

An oracle separation is easy to show. I'm not sure which paper showed it first, but for example you can already show that there exists an oracle $X$ such that

$\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$

which implies

$\mathsf{AM}^X \not\subset \mathsf{SZK}^X$

because $\mathsf{NP}$ is in $\mathsf{AM}$ and $\mathsf{SZK}$ is in $\mathsf{QSZK}$. See arXiv:1801.08967 for one way to prove this. See the comment on page 3 of arXiv:1902.03660 for another way to show this.

Also note that in the unrelativized world $\mathsf{AM=SZK}$ would collapse the polynomial hierarchy, because $\mathsf{SZK}$ is closed under complement, and hence this implies $\mathsf{AM=coAM}$, which collapses $\mathsf{PH}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.