книги Наука, техника, медицина Естественные науки Точные науки Математика Научные издания Теория вероятностей

Permanent is Sharp-P-Complete

Код 1002951

Нет в продаже

Аннотация к книге "Permanent is Sharp-P-Complete"

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

Оставить комментарий

Оцените книгу:

Издательство: Книга по требованию
Дата выхода: июль 2011
ISBN: 978-6-1312-8194-5
Объём: 84 страниц
Масса: 147 г
Размеры(высота, ширина, толщина), см: 23 x 16 x 1

Вместе с этой книгой покупают