#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
VIKTÓRIA ZANKÓ · International Journal of Foundations of Computer Science · 1991
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.