1
$\begingroup$

Does anyone know of any instances where we've been able to show that some complexity class is strictly harder than SZK relative to some oracle?

In general, it seems that SZK is really hard (for example, this paper https://arxiv.org/pdf/1609.02888.pdf shows that SZK is harder than PP relative to some oracle) and so I've been wondering if any results have been obtained in the opposite direction.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Well, certainly SZK is in IP, namely, PSPACE. At this point I cannot think of common classes, rather than PP and parityP, that are just below PSPACE. $\endgroup$ – Lwins Jul 2 '19 at 19:41

Your Answer

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

Browse other questions tagged or ask your own question.