On Arithmetic Branching Programs

摘要

The model of arithmetic branching programs is an algebraic model of computation generalizing the model of modular branching programs. We show that, up to a polynomial factor in size, arithmetic branching programs are equivalent to complements of dependency programs, a model introduced by Pudlák and Sgall. Using this equivalence we prove that dependency programs are closed under conjunction over every field, answering an open problem of theirs. Furthermore, we show that span programs, an algebraic model of computation introduced by Karchmer and Wigderson, are at least as strong as arithmetic programs; every arithmetic program can be simulated by a span program of size not more than twice the size of the arithmetic program. Using the above results we give a new proof that NL/poly⊆⊕L/poly, first proved by Wigderson [25]. Our simulation of NL/poly is more efficient, and it holds for logspace counting classes over every field.