It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.
No takes yet. Share an insight, caveat, or question.
Leslie G. Valiant (1979) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: