#P-COMPLETENESS VIA MANY-ONE REDUCTIONS

Abstract
Valiant defined #P-completeness using Turing reductions. We propose a more restrictive definition, a variant of many-one reductions, and prove that the (0, 1)-permanent remains #P-complete under this definition.