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 [1]}$ 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 [1]}$-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 [1]}$ or any of these problems before? In particular, I was surprised by being unable to find this $C_=P$-complete problem.
