On the hardness of the noncommutative determinant - Computer Science > Computational ComplexityReportar como inadecuado




On the hardness of the noncommutative determinant - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this paper we study the computational complexity of computing thenoncommutative determinant. We first consider the arithmetic circuit complexityof computing the noncommutative determinant polynomial. Then, more generally,we also examine the complexity of computing the determinant as a functionover noncommutative domains. Our hardness results are summarized below:1. We show that if the noncommutative determinant polynomial has smallnoncommutative arithmetic circuits then so does the noncommutative permanent.Consequently, the commutative permanent polynomial has small commutativearithmetic circuits. 2. For any field F we show that computing the n X npermanent over F is polynomial-time reducible to computing the 2n X 2nnoncommutative determinant whose entries are On^2 X On^2 matrices overthe field F. 3. We also derive as a consequence that computing the n X npermanent over nonnegative rationals is polynomial-time reducible to computingthe noncommutative determinant over Clifford algebras of n^{O1} dimension.Our techniques are elementary and use primarily the notion of the HadamardProduct of noncommutative polynomials.



Autor: V. Arvind, Srikanth Srinivasan

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados