PaperlayerView exact revision on arXiv

Source-linked AI summary

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

V. Arvind, Pushkar S. Joglekar

arXiv:2609.37319v1cs.CC

TL;DR

For rational circuits, RIT asks whether all inversions are legal and whether a correct circuit computes zero in the free skew field; known methods for circuits used exponential space. The method simulates the unrolled formula using a path register and reused uniformity workspace to recover each current gate, storing O(1) bits per level. Polynomial-space RIT for rational circuits over Q also places degree-unrestricted noncommutative PIT in PSPACE.

  • Problem

    For rational circuits, RIT asks whether all inversions are legal and whether a correct circuit computes zero in the free skew field; known methods for circuits used exponential space.

    Source: §1 · p. 2

  • Method

    The method simulates the unrolled formula using a path register and reused uniformity workspace to recover each current gate, storing O(1) bits per level.

    Source: §2.3 · pp. 4–5, §4.1 · p. 7

  • Results

    Polynomial-space RIT for rational circuits over Q also places degree-unrestricted noncommutative PIT in PSPACE.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper concludes that degree-unrestricted noncommutative PIT admits a polynomial-space upper bound.

    Source: §1 · p. 3

    The paper cautions that the stated biconditional relating fullness of B to fullness of A is not unconditional.

    Source: §4.2 · p. 10

Abstract

from arXiv · show

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^{\Theta(s)}$ yields a polynomial space algorithm.

1 Introduction

Rational identity testing (RIT) asks whether a rational circuit is correct and, if so, whether its value is zero in the free skew field. The paper obtains a polynomial-space algorithm by applying uniform parallel rank testing to a succinctly represented pencil.

1 Introduction

  • For a circuit of size s, unrolling to a formula yields a pencil of dimension 2^O(s), so known rank methods use exponential time and space.The introduction reports that no polynomial-space upper bound for circuit RIT was known.Source: §1 · p. 2
  • The reduction presents the exponentially large pencil succinctly: each entry can be computed from its indices using space polynomial in s.Its fullness determines the identity-testing question.Source: §1 · pp. 2–3
  • They apply Chatterjee et al.’s logspace-uniform NC2 algorithm for testing full noncommutative rank of a homogeneous pencil to a succinctly presented pencil; simulation takes deterministic space O(log2 M)+O(sO(1))=O(sO(1)), essentially polynomial in s.Source: §1 · p. 3
  • RIT for rational circuits over Q can be decided in polynomial space, including whether an inversion gate is illegal and, for correct circuits, whether the value is zero.This also places degree-unrestricted noncommutative polynomial identity testing in PSPACE.Source: §1 · p. 3

2 Uniform parallel algorithms on succinct inputs

This section gives a workspace bound for evaluating uniform parallel algorithms on inputs supplied through bit oracles, then applies it to succinct inputs. Its simulation stores a path through the circuit rather than all gate values, yielding polynomial-space consequences for succinct NC problems.

2.1 Succinct inputs

  • A succinct presentation gives the input length and a bit oracle that returns any requested input bit using bounded reusable workspace.The interface does not require the oracle to be a Boolean circuit; only its workspace enters the stated bounds.Source: §2.1 · p. 3

2.2 Uniform circuit families

  • Uniformity supplies procedures for finding the output gate, identifying gate types, and retrieving child names within bounded workspace.The paper notes that standard DLOGTIME-uniformity and logspace-uniformity conditions provide this direct-connection information.Source: §2.2 · p. 4

2 Uniform parallel algorithms on succinct inputs

  • For succinctly presented inputs, the simulation decides membership in a uniform circuit family using workspace bounded by the circuit depth, input-index length, uniformity space, and oracle workspace.The workspace components are reused where possible; the running time can be exponential in the depth.Source: §2.3 · pp. 4–5

2.3 The simulation

  • The evaluation follows a root-to-gate path, recomputes gate names as needed, and stores values only along that path.For uniform NC^i on succinct inputs of length at most 2^O(s), the corollary gives polynomial space when oracle workspace is polynomial in s.Source: §2.3 · pp. 4–5
  • When a Boolean circuit presents the succinct input, the resulting succinct version of a uniform NC^i problem is in PSPACE.The corollary applies when the presenting circuit has size s and the input has 2^n bits with n bounded by s.Source: §2.3 · p. 6

3 Rational circuits and the free skew field

The section defines rational circuits over noncommuting variables and the free skew field in which they are evaluated. It also establishes the rank and fullness notions used to characterize the circuit problem.

3.1 Inner rank and fullness

  • The free skew field is the universal field of fractions of the free associative algebra on noncommuting variables.Source: §3.1 · p. 6
  • A square matrix is full when its noncommutative rank equals its dimension, equivalently when it is invertible over the free skew field.Source: §3.1 · p. 6

3.2 Rational circuits and correctness

  • A rational circuit uses input variables or rational constants, addition, multiplication, and inversion; it is correct only when every inversion is applied to a nonzero value.A correct circuit computes an element bΦ of the free skew field.Source: §3.2 · p. 7
  • Rational constants can be replaced by integer gates using at most four times the circuit size, preserving gate values and correctness.The inserted inversions are legal because each denominator is a nonzero central scalar.Source: §3.2 · p. 7

4 From circuits to succinct pencils

A rational circuit can be represented by a large Hrubeš–Wigderson pencil whose entries remain accessible with polynomial workspace. The construction preserves the circuit’s values and correctness, allowing a succinct pencil to stand in for explicit unrolling.

4 From circuits to succinct pencils

4.1 Unrolling

  • Unrolling a size-s circuit duplicates shared subcircuits into a formula with at most 2^s nodes while preserving correctness and computed values.The unrolled formula’s nodes correspond to directed paths in the circuit, with each path recording the input port followed.Source: §4.1 · pp. 7–8

4.2 The Hrubeš–Wigderson pencil and its structure

  • The pencil’s entries contain only single symbols, and each variable occurrence contributes one distinct entry; its dimension is at most 3·2^depth(F)−1.For the unrolled subformula, the dimension is at most 3·2^(s−1)−1.Source: §4.2 · p. 9
  • The inversion-gadget fullness test is conditional: it applies when A is invertible, as guaranteed for pencils of correct formulas.Without that condition, the unconditional biconditional can fail.Source: §4.2 · p. 10
  • For a correct formula F, the wrapper pencil L(F) is non-full exactly when bF=0, and this criterion is defined syntactically even for an incorrect F.The criterion also equates bF=0 with F^-1 being incorrect.Source: §4.2 · p. 10

4.3 The entry oracle

  • The entry oracle follows a single gate-to-child path for at most s+1 steps, using O(s^2) workspace and polynomial time per query.Its output is the requested coefficient or scalar part of the queried pencil entry.Source: §4.3 · pp. 11–12

5 Homogenization

The section shows that adding a variable for the constant part of an affine pencil preserves its noncommutative rank. Consequently, fullness can be tested using the corresponding homogeneous pencil.

5 Homogenization

  • Homogenizing an affine pencil by absorbing its constant matrix into an extra variable preserves noncommutative rank and therefore preserves fullness.The affine and homogeneous pencils are full over their respective free skew fields in exactly the same cases.Source: §5 · p. 12
  • The homogeneous-pencil fullness problem is in NC^2, decided by uniform Boolean circuits of polynomial size, O(log^2 M) depth, and O(log M) uniformity space.Source: §5 · p. 12

6 Rational identity testing is in polynomial space

Rational identity testing for circuits over Q is decidable in deterministic O(s^2) workspace, including whether the circuit is correct and whether its value is zero. The proof combines a succinct linear-pencil representation with a polynomial-space simulation of a rank algorithm.

6 Rational identity testing is in polynomial space

  • The correctness check tests inversion gates in topological order, using zero tests on their arguments and reusing workspace across calls.If a test returns zero, the algorithm reports that gate; if all tests pass, it tests the output value.Source: §6 · p. 13
  • O(s^2) workspace suffices to decide whether a rational circuit over Q is correct and, if so, whether its value is zero.When the circuit is incorrect, the algorithm identifies an inversion gate whose argument evaluates to zero.Source: §6 · p. 13
  • A succinctly represented pencil for the circuit is processed by simulating the NC rank algorithm, yielding an s^O(1)-space identity test.The pencil has size 2^O(s), and its entries can be computed from indices by an s^O(1)-space algorithm.Source: §6 · p. 13
  • Noncommutative polynomial identity testing for division-free circuits of degree up to 2s is in PSPACE.The rational-circuit result also holds over any finite field.Source: §6 · p. 14
Loading 2609.37319v1…