<p>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 <span class="math-container">$X$</span> such that</p>

<blockquote>
  <p><span class="math-container">$\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$</span></p>
</blockquote>

<p>which implies </p>

<blockquote>
  <p><span class="math-container">$\mathsf{AM}^X \not\subset \mathsf{SZK}^X$</span></p>
</blockquote>

<p>because <span class="math-container">$\mathsf{NP}$</span> is in <span class="math-container">$\mathsf{AM}$</span> and <span class="math-container">$\mathsf{SZK}$</span> is in <span class="math-container">$\mathsf{QSZK}$</span>.
See <a href="https://arxiv.org/abs/1801.08967" rel="noreferrer">arXiv:1801.08967</a> for one way to prove this. See the comment on page 3 of <a href="https://arxiv.org/abs/1902.03660" rel="noreferrer">arXiv:1902.03660</a> for another way to show this.</p>

<p>Also note that in the unrelativized world <span class="math-container">$\mathsf{AM=SZK}$</span> would collapse the polynomial hierarchy, because <span class="math-container">$\mathsf{SZK}$</span> is closed under complement, and hence this implies <span class="math-container">$\mathsf{AM=coAM}$</span>, which collapses <span class="math-container">$\mathsf{PH}$</span>.</p>

CC BY-SA 4.0
2019-07-14T04:16:52.453Z
2019-07-14T04:16:52.453Z
Robin Kothari
<p>Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?</p>

<cc.complexity-theory><complexity-classes><interactive-proofs>
Separation of AM and SZK
wfawwer
# Separation of AM and SZK

(Asked by: username_0 on 2019-07-13)

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

**Tags:** cc.complexity-theory, complexity-classes, interactive-proofs

---

## 1 answers

### Answer by username_1 on 2019-07-14. Score: 6 | Accepted answer

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](https://arxiv.org/abs/1801.08967) for one way to prove this. See the comment on page 3 of [arXiv:1902.03660](https://arxiv.org/abs/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}$.


---

