1
$\begingroup$

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.

$\endgroup$

0

Your Answer

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