The problem of computing the permanent of a matrix is closely connected with another basic problem in complexity theory, namely finding a perfect matching in a bipartite graph. Thus, for a bipartite graph with 2n vertices partitioned into two parts with n vertices each, the number of perfect matchings in this graph is equal to the permanent of its biadjacency matrix and the square of the number of perfect matchings is equal to the permanent of its adjacency matrix. Since any 0-1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies that the problem of counting the number of perfect matchings in a bipartite graph is #P-complete.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.