36
$\begingroup$

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

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ Are you looking for something more than "X is NP-complete under parsimonious reductions"? $\endgroup$
    – Joshua Grochow
    Commented Jan 17, 2013 at 3:38
  • 5
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented Jan 17, 2013 at 4:46
  • 14
    $\begingroup$ But is there a problem that negates this ? i.e X is NP-complete and #X is not #P-complete ? $\endgroup$
    – Suresh Venkat
    Commented Jan 17, 2013 at 6:40
  • 8
    $\begingroup$ @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). $\endgroup$
    – Niel de Beaudrap
    Commented Jan 17, 2013 at 12:57
  • 3
    $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Commented Jan 17, 2013 at 13:36

2 Answers 2

Reset to default
30
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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