# When does “X is NP-complete” imply “#X is #P-complete”?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.

Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?

Of course the existence of a parsimonious reduction is one such condition, but this is obvious and the only such condition of which I am aware. The ultimate goal would be to show that no condition is needed.

Formally speaking, one should start with the counting problem #$X$ defined by a function $f : \{0,1\}^* \to \mathbb{N}$ and then define the decision problem $X$ on an input string $s$ as $f(s) \ne 0$?

• Are you looking for something more than "X is NP-complete under parsimonious reductions"? – Joshua Grochow Jan 17 '13 at 3:38
• @usul: No. If we drop the assumption that X is NP-complete, then bipartite matching is in P (so definitely not parsimoniously NP-complete assuming $P \neq NP$) but its counting version is #P-complete. However, if we really want X NP-complete, then off the top of my head I don't know of a problem X such that: 1) X is NP-complete, 2) X is not NP-complete under parsimonious reductions, and 3) #X is #P-complete. But I haven't really thought about it. – Joshua Grochow Jan 17 '13 at 4:46
• But is there a problem that negates this ? i.e X is NP-complete and #X is not #P-complete ? – Suresh Venkat Jan 17 '13 at 6:40
• @YoshioOkamoto: that proves that #X ∈ #P implies that X ∈ NP. It's in the wrong direction and misses the problem of completeness. What we're looking at essentially is what additional requirements are needed in order for the existence of a many-to-one reduction for decision problems in NP (for arbitrary decision problems, or from an NP-complete problem) entails the existence of a efficient counting reduction for problems in #P (for arbitrary counting problems, or from a #P-complete problem). – Niel de Beaudrap Jan 17 '13 at 12:57
• @ColinMcQuillan It could be stated in reverse. Start with a counting problem and define a decision problem from it asking if the output is nonzero. – Tyson Williams Jan 17 '13 at 13:36

The most recent paper on this question seems to be:

Noam Livne, A note on #P-completeness of NP-witnessing relations, Information Processing Letters, Volume 109, Issue 5, 15 February 2009, Pages 259–261 http://www.sciencedirect.com/science/article/pii/S0020019008003141

which gives some sufficient conditions.

Interestingly the introduction states "To date, all known NP complete sets have a defining relation which is #P complete", so the answer to Suresh's comment is "no examples are known".

Fischer, Sophie, Lane Hemaspaandra, and Leen Torenvliet. "Witness-isomorphic reductions and local search." LECTURE NOTES IN PURE AND APPLIED MATHEMATICS (1997): 207-224.

At the beginning of section 3.5, they ask the following question " In particular, are there NP-complete sets that with respect to some witness scheme are not #P -complete?"

And then they prove in Theorem 3.1 that "If there is a NP -complete set L that with respect to some witnessing relation R$_L$ is not #P-complete, then ${\bf P}$ $\not =$ ${\bf P^{\bf \#P}}$".