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?

  • $\begingroup$ 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. $\endgroup$
    – PsySp
    Oct 12 at 14:56
  • 3
    $\begingroup$ 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. $\endgroup$
    – holf
    Oct 12 at 15:12
  • $\begingroup$ @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")? $\endgroup$
    – ddr
    Oct 12 at 15:52
  • $\begingroup$ @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 ? $\endgroup$
    – ddr
    Oct 12 at 15:55
  • 2
    $\begingroup$ 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”. $\endgroup$ Oct 13 at 6:07


Your Answer

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