论文标题
真实的恒定深度电路的逻辑表征
A Logical Characterization of Constant-Depth Circuits over the Reals
论文作者
论文摘要
在本文中，我们给出了一个无私定理的实现计算。我们定义了在实数上运行的电路，并表明多项式大小和恒定深度的电路家族可以准确地确定那些可以在Cucker and Meer意义上以一阶逻辑来定义的真实载体集合。我们的表征既具有不均匀的自然均匀条件。
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 and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.
