Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete?

Question

Once we fix a polynomial time deterministic verifier V(input, certificate), its corresponding NP problem is the question: For this input, does a (polynomial size) certificate exist such that V(input, certificate) returns True?

The associated counting problem (#P class) is: How many certificates exist such that V(input, certificate) returns True?

#P is not a "decision problems" class, but a class of counting problems. The closest traditional "decision problems" class is PP, which has problems of the form: Do the majority of the certificates result in V(input, certificate) returning True?

I am interested in the decision version of the counting problem associated with a certain NP-complete problem + verifier, which would be: Given the input instance and a positive integer number K: Are there at least K different certificates such that V(input, certificate) returns True?

This decision problem is clearly equivalent to the counting version (via a Binary Search). If I am not mistaken, the class of all these "decision versions of the counting problems associated to NP problems" is exactly as hard as PP since:

1) Any of these "counting-decision" problems can be reframed as some other majority problem, by choosing an ad-hoc verifier definition where a lot of certificates are manually deemed to be True or False such that there are at least K True certificates in the original if and only if the majority is True in the resulting problem. Just as a simple example to illustrate the reduction idea, if there where 8 possible certificates, and we want to know whether there are at least 3 True ones, we might propose a different verifier having 11 possible certificates: for the 8 original ones it just checks normally, and for the other three it immediately returns True without looking at the input. Since the majority of 11 is 6, this new verifier accepts a majority of certificates exactly if the original one accepts at least 3.

Thus, all of these problems are in PP.

2) The corresponding "counting-decision" version for any PP-complete problem will obviously be PP-hard, since solving the original majority problem is simply solving the $(input, \left \lfloor \frac{ totalCertificates}{2} \right \rfloor + 1)$ problem. Thus, such problems are PP-complete.

So now, at last, can I clearly state my question, which is a "more sofisticated version" of the same idea shown in MAX,MAJ variants of NP complete problems:

Is there any NP-complete problem such that the decision version of its counting problem (which is in PP) is not PP-complete?

For example, in the case of Subset-Sum the associated decision problem I'm interested in would be: Are there at least K nonempty subsets of zero sum?

Since K is free and not limited to be near half of the certificates, the argument of the other answer does not apply.

Answer 1

Putting your question in more precise terms, you ask whether the following claim holds:

$* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count_R \text{ is PP-complete}$

Where $count_R$ is defined as follows:

$count_R=\left\{(x,k) \big| \hspace{1mm} \left\lvert\left\{y : R(x,y)\right\}\right\rvert\ge k\right\}$.

We call a relation $R(x,y)$ NP-complete if it is computable in polynomial time, and the language it defines $L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$ is NP-complete.

We talk in terms of relations, since as you mentioned, the counting version has to be defined relative to some specific verifier.

It seems that this is an open question, as (*) implies:

$** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \#R\text{ is #P-complete}$

Where $\#R(x)=\left\lvert \left\{y : R(x,y)\right\} \right\rvert$.

To see why * implies the above, let $R(x,y)$ be some NP-complete relation. Using (*), $count_R$ is PP complete, so $count_{\text{SAT}}\le_p count_R$. In that case, $\#SAT\in\mathsf{FP}^{\# R}$ and thus $\#R$ is $\# P$-complete (use binary search, where in each cutoff you apply the reduction from $count_{\text{SAT}}$ to $count_R$ and query the $\#R$ oracle on the result).

To my knowledge, (**) is currently open. See this related question from cstheory. Also related.