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?