What are the major steps in proving a problem is #P-complete?
For example, I know that showing a problem is NP-complete requires (i) showing the problem is in NP by giving a polytime verification algorithm, (ii) showing an existing NP-hard problem is polytime reducible to the given problem.
What would be the corresponding steps for a #P-completeness proof? Any resources would be helpful.
From Wikipedia I have: "By definition, a problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction..."
What makes a problem be in #P? Would reducing an exiting #P-complete problem to a given problem be enough?
A good treatment of the complexity of counting problems may be found in Moore and Mertens and Arora and Barak. In summary, the common approach to proving #P-completeness is through reduction. Given a known #P-complete problem $P_1$, if we can find an appropriate reduction of $P_1$ to $P_2$, then $P_2$ is also #P-complete.
First, appropriate means that the reduction allows us to efficiently retrieve the number of solutions to $P_1$ from the number of solutions to $P_2$. We call such a reduction counting and, specifically, parsimonious if it leaves the number of solutions unchanged.
Second, as in proving NP-completeness by reduction, the reduction should make solving $P_1$ "easy" if we could "easily" solve $P_2$. Hence the reduction should take polynomial time.
A final simple observation that makes the reduction approach work for #P-completeness more or less as it does for NP-completeness is that composing two counting reductions yields a counting reduction. Given a forest of known #P-complete problems, we can attach a new branch wherever we find it most convenient.