Subtraction-Free Complexity,Cluster Transformations,and Spanning Trees |
| |
Authors: | Sergey Fomin Dima Grigoriev Gleb Koshevoy |
| |
Institution: | 1.Department of Mathematics,University of Michigan,Ann Arbor,USA;2.CNRS, Mathématiques,Université de Lille,Villeneuve d’Ascq,France;3.Central Institute of Economics and Mathematics,Moscow,Russia |
| |
Abstract: | Subtraction-free computational complexity is the version of arithmetic circuit complexity that allows only three operations: addition, multiplication, and division. We use cluster transformations to design efficient subtraction-free algorithms for computing Schur functions and their skew, double, and supersymmetric analogues, thereby generalizing earlier results by P. Koev. We develop such algorithms for computing generating functions of spanning trees, both directed and undirected. A comparison to the lower bound due to M. Jerrum and M. Snir shows that in subtraction-free computations, “division can be exponentially powerful.” Finally, we give a simple example where the gap between ordinary and subtraction-free complexity is exponential. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|