<p>In the book Nature of Computation by Moore &amp; Mertens there is an exercise saying &quot;show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every problem in #P can be parsimoniously reduced to #A, then the corresponding existence problem A must be NP-complete&quot;. Also in the paper &quot;The complexity of counting stable marriages&quot; of Irving &amp; Leather it is proved that the problem of finding the number of stable matchings in a stable marriage problem is #P-complete by using a parsimonious reduction. However if I am not mistaken the corresponding existence problem -ie is there a stable matching in a given smp instance?- is in P and thus not NP-complete but that contradicts the statement of Moore &amp; Mertens. Where is the mistake in my way of thinking? What am I missing here?</p>

CC BY-SA 4.0
2022-10-12T14:56:10.120Z
This might be related: https://cstheory.stackexchange.com/questions/3416/p-complete-problem-whose-decision-version-is-in-p
Also, stable matching problem is not a decision problem (a stable matching always exists) and thus it is not in P for trivial reasons.
PsySp
CC BY-SA 4.0
2022-10-12T15:12:52.590Z
In Irving & Leather, the reduction is parsimonious to the problem of counting antichains in posets which is itself #P complete but *not* under parsimonious reductions (but wrt to reduction with oracle access, see [6] in Irving & Leather). Hence it does not implies that the stable matching problem is #P complete under parsimonious reductions.
holf
CC BY-SA 4.0
2022-10-12T15:52:06.757Z
@holf got it, thanks! is a reduction with oracle access equivalent to a poly-time counting reduction? I am just kind of trying to understand the definition of #P-completeness but I am a bit confussed as different books are defining it slightly differently(for example with poly-time reductions on Moore but with turing reductions on the book computers & intractability, are those type of reductions "equivalent")?
ddr
CC BY-SA 4.0
2022-10-12T15:55:07.200Z
@holf ++ or for example here https://en.wikipedia.org/wiki/%E2%99%AFP-complete it says there must be either poly-time counting reduction or turing reduction, are those equivalent? for a problem to be #P-hard is it necessary that there is a poly-time counting reduction or can there also be other type of reductions ?
ddr
CC BY-SA 4.0
2022-10-12T18:04:17.507Z
What I call with oracle is Turing reduction, I just wanted to give an hint on how it works without going into details (check [6], they give their definition of reduction). #P-completeness is indeed very sensible to the notion of reduction used and you are not the first to be puzzled by it, I will try to gather references into an answer later this week.
holf
CC BY-SA 4.0
2022-10-12T18:31:40.273Z
@holf Thank you very much! So just to clarify, is it correct to define  #P-complete problems as the problems in #P such that for every other problem A in #P there is a polynomial-time counting reduction from A to the original problem? Is that a correct definition or does it exclude any #P-complete problems?
ddr
CC BY-SA 4.0
2022-10-12T18:41:49.833Z
@holf ++ ie does the definition in my previous comment encompass all possible reductions and thus accurately describe all #P-complete problems? (where by poly-time counting reduction I mean the way it is defined here http://www.cs.cornell.edu/~sabhar/chapters/ModelCounting-SAT-Handbook-prelim.pdf or similarly at the book of Moore and here https://en.wikipedia.org/wiki/Polynomial-time_counting_reduction)
ddr
CC BY-SA 4.0
2022-10-13T06:07:47.847Z
There is no way for a single definition to encompass all types of reductions, as different reductions yield different concepts of #P-completeness. The standard definition of #P-completeness is with poly-time counting reductions. If you use another type of reduction (e.g. parsimonious, which are more restrictive, or Turing reductions, which are less restrictive), you should explicitly say “#P-complete under XXX reductions”.
Emil Jeřábek
CC BY-SA 4.0
2022-10-13T06:56:46.140Z
@EmilJeřábek but parsimonious reductions are only a special case of polynomial time counting reductions right? So in that sense poly-time counting reductions "include" parsimonious reductions. But do you mean Turing reductions are an even more general type than poly-time counting reductions? So does that mean defining #P-completeness through poly-time counting reductions excludes some problems for which there are Turing reductions but not poly-time counting reductions? Does that make the definition in my previous comment incorrect?
ddr
CC BY-SA 4.0
2022-10-13T06:58:45.677Z
@Emil Jeřábek or is okay to define it through poly-time counting reductions since as you say its the standard way to do it?
ddr
CC BY-SA 4.0
2022-10-13T08:43:36.610Z
I guess the correct question I wanted to ask was whether the definition through poly-time counting reductions encompasses all #P-complete problems. Obviously that is not the case if we define it through parsimonious reductions but is it the case if we define it through poly-time counting reductions? @Emil Jeřábek
ddr
CC BY-SA 4.0
2022-10-13T10:39:28.413Z
#P-complete problems are *defined* by poly-time counting reductions, so it encompasses all of them by definition. The definition is “correct” as it has the right balance of generality, simplicity, usefulness, and desirable properties, and it is the standard that people use. The fact that there may be problems #P-complete under Turing reductions but not under counting reductions does not make the definition wrong, it’s irrelevant. Maximizing the set of “#P-complete” problems is a rather nonsensical goal; clearly, the best reductions under that criterion are PSPACE or EXPTIME counting ...
Emil Jeřábek
CC BY-SA 4.0
2022-10-13T10:40:10.047Z
... reductions, under which *all* #P problems are #P-complete. Needless to say, this would make the whole concept pointless.
Emil Jeřábek
<cc.complexity-theory><counting-complexity><np-complete>
Question about #P-completeness and NP-completeness
ddr
# Question about #P-completeness and NP-completeness

(Asked by: username_0 on 2022-10-12)

In the book Nature of Computation by Moore & Mertens there is an exercise saying "show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every problem in #P can be parsimoniously reduced to #A, then the corresponding existence problem A must be NP-complete". Also in the paper "The complexity of counting stable marriages" of Irving & Leather it is proved that the problem of finding the number of stable matchings in a stable marriage problem is #P-complete by using a parsimonious reduction. However if I am not mistaken the corresponding existence problem -ie is there a stable matching in a given smp instance?- is in P and thus not NP-complete but that contradicts the statement of Moore & Mertens. Where is the mistake in my way of thinking? What am I missing here?

**Tags:** cc.complexity-theory, counting-complexity, np-complete
> **Comments:**
> **username_1**: This might be related: https://cstheory.stackexchange.com/questions/3416/p-complete-problem-whose-decision-version-is-in-p Also, stable matching problem is not a decision problem (a stable matching always exists) and thus it is not in P for trivial reasons.  
> **username_2**: In Irving & Leather, the reduction is parsimonious to the problem of counting antichains in posets which is itself #P complete but *not* under parsimonious reductions (but wrt to reduction with oracle access, see [6] in Irving & Leather). Hence it does not implies that the stable matching problem is #P complete under parsimonious reductions.  
> **username_0**: @holf got it, thanks! is a reduction with oracle access equivalent to a poly-time counting reduction? I am just kind of trying to understand the definition of #P-completeness but I am a bit confussed as different books are defining it slightly differently(for example with poly-time reductions on Moore but with turing reductions on the book computers & intractability, are those type of reductions "equivalent")?  
> **username_0**: @holf ++ or for example here https://en.wikipedia.org/wiki/%E2%99%AFP-complete it says there must be either poly-time counting reduction or turing reduction, are those equivalent? for a problem to be #P-hard is it necessary that there is a poly-time counting reduction or can there also be other type of reductions ?  
> **username_2**: What I call with oracle is Turing reduction, I just wanted to give an hint on how it works without going into details (check [6], they give their definition of reduction). #P-completeness is indeed very sensible to the notion of reduction used and you are not the first to be puzzled by it, I will try to gather references into an answer later this week.  
> **username_0**: @holf Thank you very much! So just to clarify, is it correct to define  #P-complete problems as the problems in #P such that for every other problem A in #P there is a polynomial-time counting reduction from A to the original problem? Is that a correct definition or does it exclude any #P-complete problems?  
> **username_0**: @holf ++ ie does the definition in my previous comment encompass all possible reductions and thus accurately describe all #P-complete problems? (where by poly-time counting reduction I mean the way it is defined here http://www.cs.cornell.edu/~sabhar/chapters/ModelCounting-SAT-Handbook-prelim.pdf or similarly at the book of Moore and here https://en.wikipedia.org/wiki/Polynomial-time_counting_reduction)  
> **username_3**: There is no way for a single definition to encompass all types of reductions, as different reductions yield different concepts of #P-completeness. The standard definition of #P-completeness is with poly-time counting reductions. If you use another type of reduction (e.g. parsimonious, which are more restrictive, or Turing reductions, which are less restrictive), you should explicitly say “#P-complete under XXX reductions”.  
> **username_0**: @EmilJeřábek but parsimonious reductions are only a special case of polynomial time counting reductions right? So in that sense poly-time counting reductions "include" parsimonious reductions. But do you mean Turing reductions are an even more general type than poly-time counting reductions? So does that mean defining #P-completeness through poly-time counting reductions excludes some problems for which there are Turing reductions but not poly-time counting reductions? Does that make the definition in my previous comment incorrect?  
> **username_0**: @Emil Jeřábek or is okay to define it through poly-time counting reductions since as you say its the standard way to do it?  
> **username_0**: I guess the correct question I wanted to ask was whether the definition through poly-time counting reductions encompasses all #P-complete problems. Obviously that is not the case if we define it through parsimonious reductions but is it the case if we define it through poly-time counting reductions? @Emil Jeřábek  
> **username_3**: #P-complete problems are *defined* by poly-time counting reductions, so it encompasses all of them by definition. The definition is “correct” as it has the right balance of generality, simplicity, usefulness, and desirable properties, and it is the standard that people use. The fact that there may be problems #P-complete under Turing reductions but not under counting reductions does not make the definition wrong, it’s irrelevant. Maximizing the set of “#P-complete” problems is a rather nonsensical goal; clearly, the best reductions under that criterion are PSPACE or EXPTIME counting ...  
> **username_3**: ... reductions, under which *all* #P problems are #P-complete. Needless to say, this would make the whole concept pointless.  

---

## 0 answers

