# Crafting ${NP}^{\#P}$-complete problems

Some related posts:

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$

I needed a complete problem for the class $${NP}^{\#P}$$ for a reduction to show the hardness of some other problems. Some examples of such problems in the literature are here:

https://arxiv.org/abs/2202.11955

https://dl.acm.org/doi/10.1145/116825.116858

None of the problems there suited my needs, so I crafted a complete problem from scratch. First, I show $${NP}^{\#P} = {NP}^{C_=P }$$ with the idea "we can non-deterministically choose answers to the oracle queries and verify the choices at the end". There, I use the following problem:

IN: Two boolean formulae $$\phi, \psi$$ on $$k \in \mathbb{N}$$ variables each.

OUT: $$True$$ if and only if $$\#SAT(\phi) = \#SAT(\psi)$$.

Which I show is $$C_=P$$-complete (containment: define NDTM which runs $$2^{k+1}$$ paths, check all valuations of $$\phi$$ on $$2^k$$ paths and $$\neg \psi$$ on the other $$2^k$$ paths; hardness: some playing with parsimony of Cook-Levin reductions).

Then, I deal with the pain of showing that the following problem is $${NP}^{C_=P }$$-complete.

IN: Positive integers $$n, m$$, a boolean formula $$\phi$$ on variables $$x_1, \dots, x_n$$ and two other boolean formulae $$\psi, \rho$$ on variables $$x_1, \dots, x_n, y_1, \dots, y_m$$.

OUT: $$True$$ if there exists a valuation $$v \colon \{ x_1, \dots, x_n \} \to \{ True, False \}$$ such that $$v(\phi)$$ holds and $$(\#SAT(v(\psi)) = \#SAT(v(\rho)))$$.

My question: has anyone seen $${NP}^{\#P} = {NP}^{C_=P }$$ or any of these problems before? In particular, I was surprised by being unable to find this $$C_=P$$-complete problem.