Quand «X est NP-complet» signifie «#X est # P-complet»?

Soit un problème (de décision) dans NP et soit # sa version de comptage. $X$ $X$

Dans quelles conditions sait-on que "X est NP-complet" "#X est # P-complet"? $\implies$

Bien sûr, l'existence d'une réduction parcimonieuse est une de ces conditions, mais c'est évident et la seule de ces conditions que je connaisse. Le but ultime serait de montrer qu'aucune condition n'est nécessaire.

Formellement, on devrait commencer par le problème de comptage # défini par une fonction puis définir le problème de décision sur une chaîne d'entrée comme ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity Tyson Williams
la source

Cherchez-vous quelque chose de plus que "X est NP-complet sous des réductions parcimonieuses"?

Joshua Grochow

@usul: Non. Si nous laissons tomber l'hypothèse que X est NP-complet, alors la correspondance bipartite est en P (donc certainement pas parcimonieusement NP-complet en supposant ) mais sa version de comptage est # P-complète. Cependant, si nous voulons vraiment X NP-complet, alors je ne connais pas de problème X tel que: 1) X est NP-complet, 2) X n'est pas NP-complet sous des réductions parcimonieuses, et 3) #X est # P-complet. Mais je n'y ai pas vraiment réfléchi.

P \neq N P

$P \neq NP$

Joshua Grochow

Mais y a-t-il un problème qui nie cela? c'est-à-dire que X est NP-complet et #X n'est pas # P-complet?

Suresh Venkat

@YoshioOkamoto: cela prouve que #X ∈ #P implique que X ∈ NP . C'est dans la mauvaise direction et passe à côté du problème d'exhaustivité. Ce que nous examinons essentiellement, c'est quelles exigences supplémentaires sont nécessaires pour que l'existence d'une réduction de plusieurs pour un pour les problèmes de décision dans NP (pour les problèmes de décision arbitraires ou à partir d'un problème NP- complet) implique l'existence d'un réduction efficace du comptage pour les problèmes dans #P (pour les problèmes de comptage arbitraires ou à partir d'un problème #P -complet).

Niel de Beaudrap

@ColinMcQuillan Cela pourrait être indiqué à l'envers. Commencez par un problème de comptage et définissez un problème de décision en lui demandant si la sortie est différente de zéro.

Tyson Williams

Réponses:

Le document le plus récent sur cette question semble être:

Noam Livne, A note on # P- exhausteness of NP-témoigning relations , Information Processing Letters, Volume 109, Issue 5, 15 février 2009, Pages 259-261 http://www.sciencedirect.com/science/article/pii/ S0020019008003141

ce qui donne des conditions suffisantes.

Il est intéressant de noter que l'introduction indique "À ce jour, tous les ensembles complets connus de NP ont une relation de définition qui est #P complète", donc la réponse au commentaire de Suresh est "aucun exemple n'est connu".

Colin McQuillan
la source

Fischer, Sophie, Lane Hemaspaandra et Leen Torenvliet. "Réductions isomorphes témoins et recherche locale." NOTES DE CONFÉRENCE EN MATHÉMATIQUES PURES ET APPLIQUÉES (1997): 207-224.

Au début de la section 3.5, ils posent la question suivante: "En particulier, existe-t-il des ensembles NP-complets qui, par rapport à certains schémas de témoins, ne sont pas #P-complets?"

Et puis ils prouvent dans le théorème 3.1 que "S'il y a un ensemble NP complet L qui par rapport à une relation témoin R n'est pas # P-complet, alors ". $_L$ ${\bf P}$ $\not =$ ${\bf P^{\bf \#P}}$

Tayfun Pay
la source