Volume 11 (2015)
Article 14 pp. 357-393

Non-Commutative Arithmetic Circuits with Division

Received: January 19, 2013

Revised: September 19, 2015

Published: December 20, 2015

Revised: September 19, 2015

Published: December 20, 2015

**Keywords:**arithmetic circuits, non-commutative rational function, skew field

**Categories:**complexity, lower bounds, circuit complexity, arithmetic circuits, non-commutative, skew field

**ACM Classification:**F.1.1,F.2.m

**AMS Classification:**68Q17, 68W30

**Abstract:**
[Plain Text Version]

$
$

We initiate the study of the complexity of arithmetic circuits with division gates over non-commuting variables.
Such circuits and formulae compute *non-commutative* rational functions, which, despite their name, can no longer be expressed as ratios of polynomials. We prove some lower and upper bounds, completeness and simulation results, as follows.

If $X$ is an $n\times n$ matrix consisting of $n^2$ distinct mutually non-commuting variables, we show that:

- $X^{-1}$ can be computed by a circuit of polynomial size.
- Every formula computing some entry of $X^{-1}$ must have size at least $2^{\Omega(n)}$.

- Assume that a non-commutative rational function $f$ can be computed by a formula of size $s$. Then there exists an invertible $2s\times 2s$-matrix $A$ whose entries are variables or field elements such that $f$ is an entry of $A^{-1}$.
- If $f$ is a non-commutative polynomial computed by a formula without inverse gates then $A$ can be taken as an upper triangular matrix with field elements on the diagonal.