Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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
up vote 20 down vote accepted

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

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".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.