Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:40:58 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:31 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 5:22:42 PM


  • HAL Id : inria-00074528, version 1



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



Record views


Files downloads