\(\#{} P\)-completeness via many-one reductions. (English) Zbl 0739.68036

Zankó, Viktória

Int. J. Found. Comput. Sci. 2, No. 1, 77-82 (1991).

Summary: 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.

MSC:

68Q15

Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

reducibility; counting; permanent