A Logical Characterization of Constant-Depth Circuits over the Reals

Timon Barlag, Heribert Vollmer

In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size a…