4
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ Have you seen this Wikipedia page? A good account is in Chapter 13 of Moore and Mertens. $\endgroup$ – Fabio Somenzi Jan 10 '18 at 4:15
  • $\begingroup$ Yes, I have, and updated the question accordingly. $\endgroup$ – neo4k Jan 10 '18 at 4:18
  • $\begingroup$ Yes, a polynomial-time counting reduction of a known #P-complete problem is enough. $\endgroup$ – Fabio Somenzi Jan 10 '18 at 4:19
  • $\begingroup$ Okay, so if there exists a #P-complete problem P1, and I reduce it to P2 in polytime, then P2 is also #P-complete? What is counting reduction -- making sure counting solutions for P2 is same as counting solutions for P1? $\endgroup$ – neo4k Jan 10 '18 at 4:20
  • $\begingroup$ As long as your reduction allows you to retrieve the number of solutions to the instance of P2 from the number of solutions to the instance of P1. If the number of solutions remains the same, your counting reduction is said to be parsimonious. $\endgroup$ – Fabio Somenzi Jan 10 '18 at 4:22
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.