We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the $\mathrm{AC}_{\mathbb{R}}$ and $\mathrm{NC}_{\mathbb{R}}$-classes for this setting. We give a theorem in the style of Immerman's theorem which shows that for these adapted formalisms, sets decided by circuits of constant depth and polynomial size are the same as sets definable by a suitable adaptation of first-order logic. Additionally, we discuss a generalization of the guarded predicative logic by Durand, Haak and Vollmer and we show characterizations for the $\mathrm{AC}_{R}$ and $\mathrm{NC}_{R}$ hierarchy. Those generalizations apply to the Boolean $\mathrm{AC}$ and $\mathrm{NC}$ hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.
翻译:我们展示了由Cucker和Meer引入的、适用于任意无限整体域的代数电路的调整构造, 并概括了用于此设置的 $\ mathrm{AC<unk> mathb{R<unk> }和$\mathrm{NC<unk> mathb{R<unk> {R<unk> $- class。 我们用 Immerman 的定理风格给出了一个理论。 这些理论显示,对于这些经调整的正规主义, 由恒定深度和多元尺寸的电路决定的集, 与经适当调整的第一阶逻辑可以确定的集相同。 此外, 我们讨论了由 Durand、 Haak 和 Vollmer 对保守的预知性逻辑的概括化, 我们展示了 $\ mathrm{AC<unk> R} 和 $\ mathrm{NC<unk> R} 等级的特征。 这些一般化适用于布洛伦 $\ mathrm{AC} $ 和 $\ mathrm{NCNC} 。 此外, 我们引入了一种形式主义, 能够将上述复杂分类与不同基本整体域加以比较。</s>