33

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

Tyson Williams
  • 4,258
  • 2
  • 23
  • 44
  • 2
    Are you looking for something more than "X is NP-complete under parsimonious reductions"? – Joshua Grochow Jan 17 '13 at 03:38
  • @Joshua is that a necessary condition? – usul Jan 17 '13 at 04:24
  • 4
    @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 04:46
  • 13
    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 06:40
  • 1
    @SureshVenkat: If #X can be solved in polynomial time, then by checking the number of solutions is zero or more, we can determine the existence of a solution in polynomial time. Am I missing something? Probably, I didn't get a point of this question. – Yoshio Okamoto Jan 17 '13 at 12:37
  • 7
    @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
  • @NieldeBeaudrap: Ah, I see. Thank you very much. – Yoshio Okamoto Jan 17 '13 at 13:04
  • 1
    The question is phrased a little imprecisely, since there is no unique counting version for a given decision problem. – Colin McQuillan Jan 17 '13 at 13:31
  • 3
    @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
  • @Tayfun, that makes it clear that the counting version is in #P, but I don't see a straightforward reason that it is #P-complete (except the case of parsimonious reductions). – usul Jan 17 '13 at 22:04
  • A result of this type "X is NP-complete implies #X is #P-complete" is proved for satisfiability problems. – Cyriac Antony Apr 26 '21 at 12:08

2 Answers2

26

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

Colin McQuillan
  • 3,546
  • 22
  • 29
7

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

Tayfun Pay
  • 2,598
  • 2
  • 18
  • 45