Logical characterizations of algebraic circuit classes over integral domains

verfasst von

Timon Barlag, Florian Chudigiewitsch, Sabrina A. Gaube

Abstract

We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the AC_ℝ and NC_ℝ 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 AC_ℝ and NC_ℝ hierarchy. Those generalizations apply to the Boolean AC and 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.

Organisationseinheit(en)

Institut für Theoretische Informatik

Externe Organisation(en)

Universität zu Lübeck

Typ

Artikel

Journal

Mathematical Structures in Computer Science

Band

34

Seiten

346-374

Anzahl der Seiten

29

ISSN

0960-1295

Publikationsdatum

13.05.2024

Publikationsstatus

Elektronisch veröffentlicht (E-Pub)

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Mathematik (sonstige), Angewandte Informatik

Elektronische Version(en)

https://doi.org/10.1017/S0960129524000136 (Zugang: Offen)