Reference: Proceedings of the 2nd Israel Symposium on Theory of Computing Systems - ISTCS '93. Pages 108-117. IEEE, 1993.
Abstract: In 1979, Valiant proved that computing the permanent of a 01-matrix is #P-complete. In this paper we present another proof for the same result. Our proof uses "black box" methodology, which facilitates its presentation. We also prove that deciding whether the permanent is divisible by a small prime is #P-hard. We conclude by proving that a polynomially bounded function can not be #P-complete under "reasonable" complexity assumptions.
Availability: Paper available as PDF (202 Kbyte).