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:



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.



Your Answer

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