On P completeness of some counting problems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1993

On P completeness of some counting problems

Nadia Creignou
  • Fonction : Auteur
Miki Hermann

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2144.pdf (513.19 Ko) Télécharger le fichier

Dates et versions

inria-00074528 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074528 , version 1

Citer

Nadia Creignou, Miki Hermann. On P completeness of some counting problems. [Research Report] RR-2144, INRIA. 1993. ⟨inria-00074528⟩
181 Consultations
101 Téléchargements

Partager

Gmail Facebook X LinkedIn More