Classes of Arithmetic Circuits Capturing the Complexity of Computing the Determinant

Seinosuke TODA  

IEICE TRANSACTIONS on Information and Systems   Vol.E75-D    No.1    pp.116-124
Publication Date: 1992/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
complexity Theory,  arithmetic circuit,  determinant,  

Full Text: PDF>>
Buy this Article

In this paper, some classes of arithmetic circuits are introduced that capture the computational complexity of computing the determinant of matrices with entries either indeterminates or constants from a field. An arithmetic circuit is just like a Boolean circuit, except that all AND and OR gates (with fan-in two) are replaced by gates realizing a multiplication and an addition, respectively, of two polynomials over some indeterminates with coefficients from the field, and the circuit computes a (formal multivariate) polynomial in the obvious sense. An arithmetic circuit is said to be skew if at least one of the inputs of each multiplication gate is either an indeterminate or a constant. Then it is shown that for all square matrices M of dimension q, the determinant of M can be computed by a skew arithmetic circuit of (q20) gates, and is shown that for all skew arithmetic circuits C of size q, the polynomial computed by C can be defined as the determinant of a square matrix M of dimension (q). Thus the size of skew arithmetic circuit is polynomially related to the dimension of square matrices when it is considered to represent multivariate polynomials in both arithmetic circuits and the determinant. The results are extended to some other classes of arithmetic circuits less restricted than skew ones, and by using such an extended result, a difference and a similarity are demonstrated between polynomials represented as the determinant of matrix of relatively small dimension and those polynomials computed by arithmetic formulas and arithmetic circuits of relatively small size and degree.