The power of commutativity
Laurent Hyafil · 1977
In this paper we show that the computation of the determinant requires an exponential number of multiplications if the commutativity of indeterminates is not allowed. The determinant can be computed in polynomial time with the commutation of indeterminates. Hence the use of commutativity can reduce a computation of exponential complexity to a computation of polynomial complexity.