%0 Journal Article %1 valiant79 %A Valiant, Leslie G. %D 1979 %J Theoretical Computer Science %K classic complexity matrix permanent %N 2 %P 189--201 %R 10.1016/0304-3975(79)90044-6 %T The Complexity of Computing the Permanent %V 8 %X 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.

@article{valiant79, abstract = {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.}, added-at = {2016-10-29T16:24:43.000+0200}, author = {Valiant, Leslie G.}, biburl = {https://www.bibsonomy.org/bibtex/27bea9f04a3cd93c1e5f568b6a54fcc34/ytyoun}, doi = {10.1016/0304-3975(79)90044-6}, interhash = {a40baef81a559136dc71744a18381a55}, intrahash = {7bea9f04a3cd93c1e5f568b6a54fcc34}, issn = {0304-3975}, journal = {Theoretical Computer Science}, keywords = {classic complexity matrix permanent}, number = 2, pages = {189--201}, timestamp = {2016-11-01T10:00:35.000+0100}, title = {The Complexity of Computing the Permanent}, volume = 8, year = 1979 }