# $\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$

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?

• 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. Mar 2, 2023 at 18:34