On P completeness of some counting problems
Nadia Creignou, Miki Hermann · 1993
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 unication theory. On the other 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. Keywords: counting class, counting problem, #P-completeness, parsimonious reduction, satisability. Partially supported by Institut National Polytechnique de Lorraine grant 910 0146 R1. 1 Introdution Counting problems represent the quantitative counterpart to decision problems. The complexity class NP and NP-complete decision problems have been e...