Noncommutativity makes determinants hard

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that A is fixed. In this case, we obtain the following dichotomy: If A / rad A is noncommutative, then computing the determinant over A is hard. “Hard” here means # P -hard over fields of characteristic 0 and Mod p P -hard over fields of characteristic p > 0. If A / rad A is commutative and the underlying field is perfect, then we can compute the determinant over A in polynomial time. We also consider the case when A is part of the input. Here the hardness is closely related to the nilpotency index of the commutator ideal of A. Our work generalizes and builds upon previous papers by Arvind and Srinivasan (STOC 2010) [1] as well as Chien et al. (STOC 2011) [5].

Authors

• Markus Bläser

Keywords

• Counting complexity
• Determinant
• Permanent
• Associative algebras