ALCOMFT-TR-03-79

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and V Vinay
Circuits on Cylinders
Århus. Work package 4. November 2003.

Abstract: We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a pimodac circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to \acczero.

Postscript file: ALCOMFT-TR-03-79.ps.gz (187 kb).