New answers tagged algebra
6
One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $n \times n$ determinant must have size $2^{\Omega(n)}$. On the other hand, the determinant is computable by commutative algebraic formulas of size $n^{O(\log n)}$.
Top 50 recent answers are included
