# P-complet problème dont la version de décision est en P

14

1) Est-il possible d'avoir une réduction parcimonieuse d'un problème # P-complet #A à un problème de comptage #B quand (la version de décision) A est NP-complet et le B est en P?

Par exemple, peut-il y avoir une réduction parcimonieuse de #SAT à #B, lorsque B est dans P?

2) Si B est dans P, quelles sont les différentes possibilités de complexité de #B?

cc.complexity-theory complexity-classes counting-complexity marjoonjan
la source

Réponses:

20

Fg28m+14mFmFFg

Voir le chapitre 18 du livre de Papadimitriou "Computational Complexity" pour une explication claire de cela.

slimton
la source
7

La réponse à la question 2 est que la complexité du problème de comptage #B peut être fondamentalement n'importe quoi (même pas nécessairement calculable). Plus précisément, la restriction que la version de décision est en P n'a aucune implication sur la complexité de la version de comptage. En effet, vous pouvez ajouter une solution fictive à tout problème de relation afin que la version de décision devienne triviale (la réponse devient toujours oui) sans changer la complexité de la version de comptage.

Tsuyoshi Ito
la source
1
pourquoi le dites-vous? "(pas même nécessairement calculable)" Il est clair que si B est un problème de décision dans P alors le #B est dans #P, directement à partir de la définition de la classe #P! mais prouver #B est aussi # P-com est important, et l'ajout de solutions factices ne devrait pas affecter la complexité du comptage. tu es d'accord?
marjoonjan
@marjoonjan: "Il est clair que si B est un problème de décision dans P alors le #B est dans #P, directement à partir de la définition de la classe #P" C'est faux. De plus, j'ai l'impression que vous pensez qu'un problème de décision B détermine uniquement le problème de comptage #B, mais ce n'est pas le cas, comme je l'ai expliqué dans cette réponse.
Tsuyoshi Ito du