Small-space analogues of Valiant's classes
Meena Mahajan and B.V. Raghavendra Rao
Abstract
In the uniform circuit model of computation, the width of a boolean
circuit exactly characterises the "space" complexity of the computed
function. Looking for a similar relationship in Valiant's algebraic
model of computation, we propose width of an arithmetic circuit as a
possible measure of space. We introduce the class VL as an algebraic
variant of deterministic log-space L. In the uniform setting, we show
that our definition coincides with that of VPSPACE at polynomial width.
Further, to define algebraic variants of non-deterministic space-bounded
classes, we introduce the notion of "read-once" certificates for
arithmetic circuits. We show that polynomial-size algebraic branching
programs can be expressed as a read-once exponential sum over
polynomials in VL, i.e. VBP is in (Sigma^R VL). We also show that
(Sigma^R VBP) = VBP, i.e. VBPs are stable under read-once exponential
sums. Further, we show that read-once exponential sums over a restricted
class of constant-width arithmetic circuits are within VQP, and this is
the largest known such subclass of poly-log-width circuits with this
property.