# Question about #P-completeness and NP-completeness

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?

• This might be related: cstheory.stackexchange.com/questions/3416/… Also, stable matching problem is not a decision problem (a stable matching always exists) and thus it is not in P for trivial reasons. Oct 12, 2022 at 14:56
• 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
Oct 12, 2022 at 15:12
• @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
Oct 12, 2022 at 15:52
• @holf ++ or for example here 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
Oct 12, 2022 at 15:55
• 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”. Oct 13, 2022 at 6:07