<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.7279" rel="noreferrer">Fischer, Sophie, Lane Hemaspaandra, and Leen Torenvliet. "Witness-isomorphic reductions and local search." LECTURE NOTES IN PURE AND APPLIED MATHEMATICS (1997): 207-224.</a></p>

<p>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?"</p>

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

CC BY-SA 3.0
2017-05-24T18:17:28.040Z
2017-05-24T18:17:28.040Z
Tayfun Pay
<p>The most recent paper on this question seems to be:</p>

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

<p>which gives some sufficient conditions.</p>

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

CC BY-SA 3.0
2013-01-17T13:03:19.437Z
2013-01-17T13:03:19.437Z
Colin McQuillan
<p>Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2013-01-17T03:38:28.560Z
Are you looking for something more than "X is NP-complete under parsimonious reductions"?
Joshua Grochow
CC BY-SA 3.0
2013-01-17T04:24:34.023Z
@Joshua is that a necessary condition?
usul
CC BY-SA 3.0
2013-01-17T04:46:57.013Z
@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
CC BY-SA 3.0
2013-01-17T06:40:03.723Z
But is there a problem that negates this ? i.e X is NP-complete and #X is not #P-complete ?
Suresh Venkat
CC BY-SA 3.0
2013-01-17T12:37:33.410Z
@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
CC BY-SA 3.0
2013-01-17T12:57:46.423Z
@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
CC BY-SA 3.0
2013-01-17T13:04:09.330Z
@NieldeBeaudrap: Ah, I see. Thank you very much.
Yoshio Okamoto
CC BY-SA 3.0
2013-01-17T13:31:21.137Z
The question is phrased a little imprecisely, since there is no unique counting version for a given decision problem.
Colin McQuillan
CC BY-SA 3.0
2013-01-17T13:36:10.860Z
@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
CC BY-SA 3.0
2013-01-17T22:04:12.633Z
@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
CC BY-SA 4.0
2021-04-26T12:08:31.287Z
A result of this type "X is NP-complete implies #X is #P-complete" is proved for satisfiability problems.
Cyriac Antony
CC BY-SA 4.0
2024-10-04T23:40:22.367Z
Didn't Umesh Vazirani and Valiant show (around 1986) that USAT (unique SAT, where at most one satisfying assignment exists) is NP-Complete (under the mild assumption that BPP=P)?
That to me would suggest that the counting variant of this problem would be at most as hard as NP.
Yann Tal
<cc.complexity-theory><np-hardness><counting-complexity>
When does "X is NP-complete" imply "#X is #P-complete"?
Tyson Williams
# When does "X is NP-complete" imply "#X is #P-complete"?

(Asked by: username_0 on 2013-01-17)

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

**Tags:** cc.complexity-theory, np-hardness, counting-complexity
> **Comments:**
> **username_1**: Are you looking for something more than "X is NP-complete under parsimonious reductions"?  
> **username_2**: @Joshua is that a necessary condition?  
> **username_1**: @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.  
> **username_3**: But is there a problem that negates this ? i.e X is NP-complete and #X is not #P-complete ?  
> **username_4**: @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.  
> **username_5**: @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).  
> **username_4**: @NieldeBeaudrap: Ah, I see. Thank you very much.  
> **username_6**: The question is phrased a little imprecisely, since there is no unique counting version for a given decision problem.  
> **username_0**: @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.  
> **username_2**: @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).  
> **username_7**: A result of this type "X is NP-complete implies #X is #P-complete" is proved for satisfiability problems.  
> **username_8**: Didn't Umesh Vazirani and Valiant show (around 1986) that USAT (unique SAT, where at most one satisfying assignment exists) is NP-Complete (under the mild assumption that BPP=P)? That to me would suggest that the counting variant of this problem would be at most as hard as NP.  

---

## 2 answers

### Answer by username_6 on 2013-01-17. Score: 30 | Accepted answer

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


---

### Answer by username_9 on 2017-05-24. Score: 9

[Fischer, Sophie, Lane Hemaspaandra, and Leen Torenvliet. "Witness-isomorphic reductions and local search." LECTURE NOTES IN PURE AND APPLIED MATHEMATICS (1997): 207-224.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.7279)

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


---

