Deterministic polynomial identity testing in non-commutative models (Q1781113)

The authors give a deterministic polynomial time algorithm for zero testing of polynomials in non-commutative variables given by arithmetic formulae. A similar deterministic algorithm determines in polynomial time whether or not the output of a pure set-multilinear arithmetic circuit is identically 0. It is also proved that any pure circuit computing the permanent or the determinant of an \(n\times n\)-matrix has size \(2^{\Omega (n)}\). The proofs are based on the partial derivative method introduced by \textit{N. Nisan} and \textit{A. Wigderson} [Comput. Complexity 6, 217--234 (1997; Zbl 0890.68074)]. The idea is that the space spanned by all partial derivatives of a non-commutative polynomial \(f\) is of small dimension, provided that \(f\) is computed by a small arithmetic formula. A procedure to recursively check whether or not the relevant partial derivatives are identically 0 is also needed. Similar techniques have been already used by \textit{S. Waack} [``On the descriptive and algorithmic power of parity ordered binary decision diagrams'', Lect. Notes Comput. Sci. 1200, 201--212 (1997)].