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

$\endgroup$
  • 2
    $\begingroup$ Are you looking for something more than "X is NP-complete under parsimonious reductions"? $\endgroup$ – Joshua Grochow Jan 17 '13 at 3:38
  • 3
    $\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 Jan 17 '13 at 4:46
  • 13
    $\begingroup$ But is there a problem that negates this ? i.e X is NP-complete and #X is not #P-complete ? $\endgroup$ – Suresh Venkat Jan 17 '13 at 6:40
  • 6
    $\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 Jan 17 '13 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 Jan 17 '13 at 13:36
23
$\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".

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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