Computing algebraic formulas with a constant number of registers
Richard Cleve · 1988
We show that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs which use only 3 registers (or 4 registers, depending on some definitions). We also show that polynomial-length products of 3 × 3 matrices compute precisely those functions that polynomial-size formulas compute (whereas, for general rings, polynomial-length 3-register straight-line programs compute strictly more functions than polynomial-size formulas). This can be viewed as an extension of the results of Barrington in [Ba1,Ba2] from the Boolean setting to the algebraic setting of an arbitrary ring.