patternMinor
Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete?
Viewed 0 times
problemsuchthecountingversioncompletedecisionthatitsthere
Problem
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 corre
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 corre
Solution
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.
$* \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.
Context
StackExchange Computer Science Q#66586, answer score: 3
Revisions (0)
No revisions yet.