Descriptive Complexity of #AC^0 Functions

DOI10.4230/LIPIcs.CSL.2016.20zbMath1369.68220arXiv1604.06617OpenAlexW2549538997MaRDI QIDQ5278406

Juha Kontinen, Anselm Haak, Arnaud Durand, Heribert Vollmer

Publication date: 19 July 2017

Full work available at URL: https://arxiv.org/abs/1604.06617

zbMATH Keywords

finite model theoryarithmetic circuitsSkolem functioncounting classesFagin's theorem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (3)

Unnamed Item ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ Counting of Teams in First-Order Team Logics

This page was built for publication: Descriptive Complexity of #AC^0 Functions