https://hal.inria.fr/inria-00074528Creignou, NadiaNadiaCreignouHermann, MikiMikiHermannINRIA Lorraine - Inria - Institut National de Recherche en Informatique et en AutomatiqueOn P completeness of some counting problemsHAL CCSD1993counting classcounting problem#P-completenessparsimonious reductionsatisfiability[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]Inria, Rapport De Recherche2006-05-24 15:40:582022-10-26 08:16:312006-05-31 14:24:32enReportsapplication/pdf1We 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.