I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that are in this class? I was hoping to see something on Complexity Zoo but there doesn't seem to be a dedicated entry there.

The same article also demonstrates that the problem of deciding whether loop-free programs are $(\varepsilon, \delta)$-differentially private is contained within $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$. How should I understand this complexity class? I know that $\mathsf{coNP}^{\mathsf{\#P}}$ are problems that can be solved by $\mathsf{coNP}$ algorithms with access to a $\#\mathsf{P}$ oracle. But I'm not sure how to interpret the double exponent notation. What does the second oracle do (and why is it not redundant, since there is already a $\#\mathsf{P}$ oracle), and what additional computational powers does it add? Are there any interesting $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$-complete problems?

  • 1
    $\begingroup$ Just like with regular exponential notation, it’s bracketed $\mathsf{coNP^{(\#P^{\#P})}}$, not $\mathsf{(coNP^{\#P})^{\#P}}$. And the more complicated definition a class has, the less likely it is to have interesting complete problems not artificially cooked up for that purpose. $\endgroup$ Mar 2, 2023 at 18:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.