2
$\begingroup$

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?

Improve this question
$\endgroup$
13
  • $\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, 2022 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, 2022 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, 2022 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, 2022 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$
    – Emil Jeřábek
    Oct 13, 2022 at 6:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.