The complexity of computing the permanent |
| |
| Authors: | L.G. Valiant |
| |
| Affiliation: | Computer Science Department, University of Edinburgh, Edinburgh EH9 3JZ, Scotland |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
