Rational identity testing for noncommutative circuits uses polynomial space
Rational Identity Testing for Noncommutative Circuits is in Polynomial Space
Computational Complexity
Summary
Rational identity testing checks if a complex algebraic expression built from noncommuting variables equals zero. For simple expressions (formulas), this was known to be doable quickly, but for more complex ones (circuits), it was thought to need a lot of time and memory. The authors showed that even for complicated circuits, the problem can be solved using only a reasonable amount of memory (polynomial space). They use clever ways to represent big mathematical objects compactly and simulate efficient algorithms within this memory limit.
What this means in practice
- •For software engineers in symbolic computation: Check complex noncommutative algebraic expressions for equivalence or zero without excessive memory use, improving tool efficiency.
- •For hardware verification teams: Use the result to verify properties of circuits involving noncommuting operations within manageable memory constraints.
A theory result. No direct application yet.
Authors
V. Arvind, Pushkar S. Joglekar
Abstract
The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{Θ(s)}$ yields a polynomial space algorithm.