Existe-t-il un problème NP-complet, tel que la version de décision de son problème de comptage n'est pas PP-complète?

Une fois que nous avons fixé un vérificateur déterministe du temps polynomial V (entrée, certificat), son problème NP correspondant est la question: pour cette entrée, existe-t-il un certificat (taille polynomiale) tel que V (entrée, certificat) renvoie Vrai?

Le problème de comptage associé (classe #P) est: combien de certificats existent de telle sorte que V (entrée, certificat) renvoie Vrai?

#P n'est pas une classe de "problèmes de décision", mais une classe de problèmes de comptage. La classe de "problèmes de décision" traditionnelle la plus proche est PP, qui a des problèmes de forme: la majorité des certificats a-t-elle pour résultat V (entrée, certificat) True?

Je suis intéressé par la version de décision du problème de comptage associé à un certain problème NP-complet + vérificateur, qui serait: étant donné l'instance d'entrée et un nombre entier positif K: y a-t-il au moins K certificats différents tels que V (entrée, certificat) renvoie Vrai?

Ce problème de décision est clairement équivalent à la version de comptage (via une recherche binaire). Si je ne me trompe pas, la classe de toutes ces "versions de décision des problèmes de comptage associés aux problèmes NP" est exactement aussi difficile que PP puisque:

1) N'importe lequel de ces problèmes de "décision de comptage" peut être recadré comme un autre problème majoritaire, en choisissant une définition de vérificateur ad hoc où un grand nombre de certificats sont manuellement jugés Vrai ou Faux de sorte qu'il existe au moins K certificats Vrai dans l'original si et seulement si la majorité est vraie dans le problème résultant. Juste comme exemple simple pour illustrer l'idée de réduction, s'il y a 8 certificats possibles, et nous voulons savoir s'il y en a au moins 3 vrais, nous pourrions proposer un vérificateur différent ayant 11 certificats possibles: pour les 8 originaux, il suffit vérifie normalement, et pour les trois autres, il renvoie immédiatement True sans regarder l'entrée. Puisque la majorité de 11 est 6, ce nouveau vérificateur accepte la majorité des certificats exactement si l'original en accepte au moins 3.

Ainsi, tous ces problèmes sont en PP.

2) La version correspondante de "décision de comptage" pour tout problème PP-complet sera évidemment PP-difficile, car résoudre le problème de la majorité d'origine est simplement résoudre le $(input, \left \lfloor \frac{ totalCertificates}{2} \right \rfloor + 1)$problème. Ainsi, ces problèmes sont PP-complets.

Alors maintenant, enfin, puis-je formuler clairement ma question, qui est une "version plus sophistiquée" de la même idée montrée dans les variantes MAX, MAJ de problèmes complets NP :

Existe-t-il un problème NP-complet tel que la version de décision de son problème de comptage (qui est en PP) n'est pas PP-complète?

Par exemple, dans le cas de Subset-Sum, le problème de décision associé qui m'intéresse serait: Y a-t-il au moins K sous-ensembles non vides de somme nulle?

Puisque K est gratuit et n'est pas limité à près de la moitié des certificats, l'argument de l'autre réponse ne s'applique pas.

En posant votre question en termes plus précis, vous vous demandez si la revendication suivante est valable:

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

Où $count_R$ est défini comme suit:

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

Nous appelons une relation $R(x,y)$ NP-complet s'il est calculable en temps polynomial et le langage qu'il définit $L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$ est NP-complet.

Nous parlons en termes de relations, car comme vous l'avez mentionné, la version de comptage doit être définie par rapport à un vérificateur spécifique.

Il semble que ce soit une question ouverte, comme (*) implique:

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

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

Pour voir pourquoi * implique ce qui précède, laissez $R(x,y)$être une relation NP-complète. En utilisant (*),$count_R$ est PP complet, donc $count_{\text{SAT}}\le_p count_R$. Dans ce cas,$\#SAT\in\mathsf{FP}^{\# R}$ Et ainsi $\#R$ est $\# P$-complet (utilisez la recherche binaire, où dans chaque seuil vous appliquez la réduction de $count_{\text{SAT}}$ à $count_R$ et interroger le $\#R$ oracle sur le résultat).

À ma connaissance, (**) est actuellement ouvert. Voir cette question connexe de cstheory. Également lié .