On P completeness of some counting problems

Abstract : We prove that the counting problems #1-in-3Sat, #Not-All-Equal 3Sat and #3-Colorability, whose decision counterparts have been the most frequently used in proving NP-hardness of new decision problems, are #P-complete. On one hand, the explicit #P-completeness proof of #1-in-3Sat could be useful to prove complexity results within unification theory. On the ither hand, the fact that #3-Colorability is #P-complete allows us to deduce immediately that the enumerative versions of a large class of NP-complete problems are #P-complete. Moreover, our proofs shed some new light on the interest of exhibiting linear reductions between NP problems.
Type de document :
Rapport
[Research Report] RR-2144, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074528
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:40:58
Dernière modification le : samedi 17 septembre 2016 - 01:06:53
Document(s) archivé(s) le : mardi 12 avril 2011 - 17:22:42

Fichiers

Identifiants

  • HAL Id : inria-00074528, version 1

Collections

Citation

Nadia Creignou, Miki Hermann. On P completeness of some counting problems. [Research Report] RR-2144, INRIA. 1993. 〈inria-00074528〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

87