Open AccessCircuits on Cylinders
Author(s) -
Kristoffer Arnsfelt Hansen,
Peter Bro Miltersen,
V. Vinay
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i50.21765
Subject(s) - nondeterministic algorithm , constant (computer programming) , mathematics , polynomial , branching (polymer chemistry) , function (biology) , electronic circuit , discrete mathematics , combinatorics , mathematical analysis , physics , computer science , materials science , quantum mechanics , evolutionary biology , composite material , biology , programming language
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi_2 o MOD o AC^0 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 ACC^0.